Welcome Guest ( Log In | Register )

Outline · [ Standard ] · Linear+

 need help with adding numbers

views
     
TSbadai
post Jan 26 2016, 06:01 PM, updated 9y ago

Enthusiast
*****
Senior Member
986 posts

Joined: Jan 2003
You have this list of 109 numbers:

20
100
500
100
100
1900
100.13
200
200
300
140
100
2700
967.93
100
100
4000
100
100
100
1000
100
200
300
100
200
100
3000
508.47
20
100
100
100
100
2445
462.96
195
1000
300
100
100
20
595.17
250
10
10
3000
668
113.29
1374.68
204.39
697.98
1572.19
253
500
700
500
1100
142.37
2000
475
1850
495
2700
2260.78
500
1270
362.82
1951
444.03
1460
2700
425
2208.98
2700
500
1950
1400
500
2060
2270
1837
2053
751.63
1000
450
1800
1962.93
465
250
2045
300
480
462.87
2470
1514
518.17
3000
2190.93
2600
500
500
500
1004.24
1625
500
2400
2450
780

I need an algorithm to add only 8 of the numbers, and you will get the total of 15629.14.

Any taker?

to put those numbers in array, use this: 20,100,500,100,100,1900,100.13,200,200,300,140,100,2700,967.93,100,100,4000,100,100,100,1000,100,200,300,100,200,100,3000,508.47,20,100,100,100,100,2445,462.96,195,1000,300,100,100,20,595.17,250,10,10,3000,668,113.29,1374.68,204.39,697.98,1572.19,253,500,700,500,1100,142.37,2000,475,1850,495,2700,2260.78,500,1270,362.82,1951,444.03,1460,2700,425,2208.98,2700,500,1950,1400,500,2060,2270,1837,2053,751.63,1000,450,1800,1962.93,465,250,2045,300,480,462.87,2470,1514,518.17,3000,2190.93,2600,500,500,500,1004.24,1625,500,2400,2450,780

TQ TQ TQ
dreambox
post Jan 26 2016, 06:05 PM

New Member
*
Junior Member
18 posts

Joined: Dec 2015
Google knapsack problem.

The problem you've described is exactly that and the solution is already widely available.
TSbadai
post Jan 26 2016, 06:16 PM

Enthusiast
*****
Senior Member
986 posts

Joined: Jan 2003
knapsack problem is when you have fixed items and try to load max volume. mine have fixed volume (15629.14) and fixed items (8).

This post has been edited by badai: Jan 26 2016, 06:21 PM
alien3d
post Jan 26 2016, 07:47 PM

Look at all my stars!!
*******
Senior Member
3,740 posts

Joined: Mar 2009
QUOTE(badai @ Jan 26 2016, 06:16 PM)
knapsack problem is when you have fixed items and try to load max volume. mine have fixed volume (15629.14) and fixed items (8).
*
so just random.No way i would test one by one.this is php

CODE

$test =array();
$d=0;
$arrayValue = array(20,100,500,100,100,1900,100.13,200,200,300,140,100,2700,967.93,100,100,4000,100,100,100,1000,100,200,300,100,200,100,3000,508.47,20,100,100,100,100,2445,462.96,195,1000,300,100,100,20,595.17,250,10,10,3000,668,113.29,1374.68,204.39,697.98,1572.19,253,500,700,500,1100,142.37,2000,475,1850,495,2700,2260.78,500,1270,362.82,1951,444.03,1460,2700,425,2208.98,2700,500,1950,1400,500,2060,2270,1837,2053,751.63,1000,450,1800,1962.93,465,250,2045,300,480,462.87,2470,1514,518.17,3000,2190.93,2600,500,500,500,1004.24,1625,500,2400,2450,780);
for($k=0;$k<100000000;$k++) {
$sum=0;
$test=array();
for($i=0;$i<8;$i++) {
$j = $arrayValue[array_rand($arrayValue)];
 $test[]=$j;
 $sum+=$j;
}
if($sum == 15629.14) {
 $d = $k;
    break;
}else{
 echo $k."sum was".$sum."\n";
}
$test = null;
}
echo "try".$d;
echo var_dump($test);



This post has been edited by alien3d: Jan 26 2016, 10:15 PM
angch
post Jan 26 2016, 09:27 PM

On my way
****
Junior Member
635 posts

Joined: Jul 2006
CODE
go run pick8.go
Found it in 96181218 tries
2445
1572.19
2260.78
2270
1962.93
1514
2600
1004.24


Quick hack, sorry the messy stuff. Run time is
CODE
real 1m41.097s
user 2m17.709s
sys 0m7.243s


UPDATE: Doing things a little more intelligently and reducing the number of checks:
CODE
go run pick8.go
Found it in 43369955 tries
1004.24
1572.19
1950
1951
2000
2190.93
2260.78
2700

real 0m18.630s
user 0m19.583s
sys 0m1.034s


(yes, there's more than one solution, and we just output the first one we see and get out -- we're not looking for optimal solutions ala knapsack)

https://gist.github.com/angch/ea9cea934ee8ca6cab6a

Attachment contains the source, and binaries for Linux (64bit), OS X (64 bit), and Windows (64bit? dunno).

IPB messed up my formatting, use link above to preview properly.
CODE
// https://forum.lowyat.net/topic/3852732

// Quick and Dirty hack
// angch's go kata

// Original idea was to scale up and use Go channels, but we can't do
// priority queue that way.

package main

import (
"container/heap"
"fmt"
"sort"
)

// Current picks, and their sum so far
type Picks struct {
priority float32 // The priority of the item in the queue.
index    int     // The index of the item in the heap.

idx []int   // Not to be confused with idx, which is a set of the items we picked
sum float32 // sum so far
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Picks

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Picks)
item.index = n
*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}

func initTestItems() []float32 {
items := make([]float32, 0, 0)

items = append(items, 1.0)
items = append(items, 2.0)
items = append(items, 3.0)
items = append(items, 4.0)
items = append(items, 2.2)
items = append(items, 0.5)
items = append(items, 0.5)
return items
}

func initItems() []float32 {
i := []float64{20, 100, 500, 100, 100, 1900, 100.13, 200, 200, 300, 140, 100, 2700, 967.93, 100, 100, 4000, 100, 100, 100, 1000, 100, 200, 300, 100, 200, 100, 3000, 508.47, 20, 100, 100, 100, 100, 2445, 462.96, 195, 1000, 300, 100, 100, 20, 595.17, 250, 10, 10, 3000, 668, 113.29, 1374.68, 204.39, 697.98, 1572.19, 253, 500, 700, 500, 1100, 142.37, 2000, 475, 1850, 495, 2700, 2260.78, 500, 1270, 362.82, 1951, 444.03, 1460, 2700, 425, 2208.98, 2700, 500, 1950, 1400, 500, 2060, 2270, 1837, 2053, 751.63, 1000, 450, 1800, 1962.93, 465, 250, 2045, 300, 480, 462.87, 2470, 1514, 518.17, 3000, 2190.93, 2600, 500, 500, 500, 1004.24, 1625, 500, 2400, 2450, 780}
sort.Sort(sort.Float64Slice(i))
items := make([]float32, len(i))
for k, v := range i {
 items[k] = float32(v)
}
return items
}

func search(items []float32, target float32, targetNumber int) {
checks := 0

// Create a priority queue, put the items in it, and
// establish the priority queue (heap) invariants.
pq := make(PriorityQueue, len(items))
i := 0
for idx, number := range items {
 priority := float32(0)
 if target > number {
  priority = number - target // yes, it's negative
 }
 pq[i] = &Picks{
  priority: priority,
  index:    idx,
  idx:      []int{idx},
  sum:      number,
 }
 i++
 checks++
}
heap.Init(&pq)

for pq.Len() > 0 {
 picks := heap.Pop(&pq).(*Picks)

 if picks.sum == target &&
  len(picks.idx) == targetNumber {
  fmt.Println("Found it in", checks, "tries")
  for _, v := range picks.idx {
   fmt.Println(items[v])
  }
  return
 }

 lastIdx := picks.idx[len(picks.idx)-1]
 if len(picks.idx) >= targetNumber {
  continue
 }

 for lastIdx++; lastIdx < len(items); lastIdx++ {
  number := items[lastIdx]
  priority := float32(0)
  if target > number {
   priority = number - target // yes, it's negative
  }
  if target < number {
   continue
  }

  indices := make([]int, len(picks.idx)+1)
  copy(indices, picks.idx)
  indices[len(picks.idx)] = lastIdx

  newPick := &Picks{
   priority: priority,
   idx:      indices,
   sum:      picks.sum + number,
  }
  heap.Push(&pq, newPick)
  checks++
 }
}
fmt.Println("Give up after", checks, "tries")
}

func main() {
//items := initTestItems()
items := initItems()
//search(items, 5.0, 3)
search(items, 15629.14, 8)
}


This post has been edited by angch: Jan 26 2016, 10:52 PM


Attached File(s)
Attached File  pick8.zip ( 1.56mb ) Number of downloads: 2
alien3d
post Jan 26 2016, 10:17 PM

Look at all my stars!!
*******
Senior Member
3,740 posts

Joined: Mar 2009
angch 25% my proc usage lol running php code
angch
post Jan 26 2016, 10:39 PM

On my way
****
Junior Member
635 posts

Joined: Jul 2006
It's a subset of the subset sum problem, where the length of the subset is fixed. https://en.wikipedia.org/wiki/Subset_sum_problem

In the solution above, we're exploiting that fact instead of more traditional dynamic programming type solution (see https://gist.github.com/angch/694e420a53abe35a5230 ) Haven't tried it, but the amount of memory it requires for that many items would be much larger. In our case, we make sure of the fact that the target number of items in the subset, is 8, which is significantly smaller than the number of given items.

So we iterate through possible permutations, but rather than naively going through them, we pick the closest solution and organise all the potential solutions in a priority queue and evaluate that. Bad potential solutions, when we reach 8 too quickly, we just dump that and move to the next candidate.

A fixed, sorted version of the above now runs in about 18 seconds. Single core. We can probably scale up to N cores by sharding our priority queues.

TSbadai
post Jan 27 2016, 10:54 AM

Enthusiast
*****
Senior Member
986 posts

Joined: Jan 2003
thanks angch.

need to translate that to PHP though. will need to run it lots of time. got few more to solved.
TSbadai
post Jan 27 2016, 03:14 PM

Enthusiast
*****
Senior Member
986 posts

Joined: Jan 2003
took forever when want to select 70 numbers from 117. who got super computer here?
alien3d
post Jan 27 2016, 05:19 PM

Look at all my stars!!
*******
Senior Member
3,740 posts

Joined: Mar 2009
QUOTE(badai @ Jan 27 2016, 10:54 AM)
thanks angch.

need to translate that to PHP though. will need to run it lots of time. got few more to solved.
*
lol.. you don't see my code was php ?be warn ... it will slow.

This post has been edited by alien3d: Jan 27 2016, 06:29 PM
angch
post Jan 27 2016, 11:09 PM

On my way
****
Junior Member
635 posts

Joined: Jul 2006
QUOTE(badai @ Jan 27 2016, 03:14 PM)
took forever when want to select 70 numbers from 117. who got super computer here?
*
It's between the keyboard and the chair. If you look at your dataset properly, you'll find lots of ways to cheat and optimize.

The trick is not to evaluate everything and skip whole sets of combinations.

e.g. For your original problem, a more optimized version of my program ran in 9 to 10 seconds. But if you realized to get the 0.14 in your sum, you probably need these four: 1004.24 + 1572.19 + 2190.93 + 2260.78 = 7028.14 So you skip testing for those four.

So taking that into account, it ran in 0.5 seconds.

CODE
go run pick8.go
Sorted items are [10 10 20 20 20 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100.13 113.29 140 142.37 195 200 200 200 200 204.39 250 250 253 300 300 300 300 362.82 425 444.03 450 462.87 462.96 465 475 480 495 500 500 500 500 500 500 500 500 500 500 508.47 518.17 595.17 668 697.98 700 751.63 780 967.93 1000 1000 1000 1004.24 1100 1270 1374.68 1400 1460 1514 1572.19 1625 1800 1837 1850 1900 1950 1951 1962.93 2000 2045 2053 2060 2190.93 2208.98 2260.78 2270 2400 2445 2450 2470 2600 2700 2700 2700 2700 3000 3000 3000 4000]
Length of items: 109
Looking for subset length 9 summing to 15629.14
Using heuristics optimisation to skip testing the items in the known subset
New items is [10 10 20 20 20 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100.13 113.29 140 142.37 195 200 200 200 200 204.39 250 250 253 300 300 300 300 362.82 425 444.03 450 462.87 462.96 465 475 480 495 500 500 500 500 500 500 500 500 500 500 508.47 518.17 595.17 668 697.98 700 751.63 780 967.93 1000 1000 1000 1100 1270 1374.68 1400 1460 1514 1625 1800 1837 1850 1900 1950 1951 1962.93 2000 2045 2053 2060 2208.98 2270 2400 2445 2450 2470 2600 2700 2700 2700 2700 3000 3000 3000 4000]
New target is 8601 , 5
Found it in 132768 tries, skipped 11380 times
1400
1514
1837
1900
1950
1004.24
1572.19
2190.93
2260.78
Max pq len is 106

real 0m0.520s
user 0m0.555s
sys 0m0.102s


Good luck trying that in PHP. Solution I posted is generic anyway, easily adapted to any inputs and targets. Bulk of the CPU time is spent managing the priority queue and array allocation. Not linking my optimized solution because no one cares anyway.

Bear in mind the running time is exponential to your "number of items picked".
kingkingyyk
post Jan 29 2016, 03:42 PM

10k Club
Group Icon
Elite
15,425 posts

Joined: Mar 2008
QUOTE(badai @ Jan 26 2016, 06:16 PM)
knapsack problem is when you have fixed items and try to load max volume. mine have fixed volume (15629.14) and fixed items (8).
*
Hi, it is possible to transform your question to knapsack problem. Rather than maximum, we also can find minimum with it. The value used would be abs(sum - target number). smile.gif

This post has been edited by kingkingyyk: Jan 29 2016, 03:43 PM

 

Change to:
| Lo-Fi Version
0.0176sec    0.74    6 queries    GZIP Disabled
Time is now: 29th March 2024 - 08:06 PM