Prev: Chopard Mille Miglia GMT Chronograph Mens Watch 16/8992/3
Next: Sorting of Base64 strings
From: jeffbg123 on 30 Jun 2008 13:38
Hey,

I am trying to figure out the quickest way to do the following.

You are given a list of integers, a goal sum (integer), and an
acceptable +/- (integer).

The goal is to find a list of integers, all from the first list (all
unique) that sum up to the goal sum plus or minus the acceptable
range.

Example:

list: 1,2,3,4,5,6,7,8,9
Goal: 8
+/-: 1

It would output one of the following, whichever it found first:
1,2,4
1,3,4
1,6
1,7
........etc

Basically whatever numbers sum to 7,8, or 9

Make sense?

Is there a quick way of doing this? Notably faster than brute force?

Thanks,

-Jeff
From: gw7rib on 30 Jun 2008 14:22
On 30 Jun, 18:38, jeffbg123 <jeffbg...(a)gmail.com> wrote:
> The goal is to find a list of integers, all from the first list (all
> unique) that sum up to the goal sum plus or minus the acceptable
> range.

If you have to get exactly the goal, then there is no quick general
solution - the problem is "NP hard". I'm not sure whether having an
acceptable range, instead of a single value, is going to help,
however.

Try googling for "knapsack problem", which should give you some leads.

Hope that helps.
Paul.
From: jeffbg123 on 30 Jun 2008 15:20
Thanks for the advice Paul.

I am hesitant to accept solutions that are efficient for the knapsack
problem as I would suspect it would be an easier solution when all of
the values of the items are exactly the same. You do not gain anything
from adding the largest item over the smallest item. And you are not
going for the most songs, you are going to try to get the knapsack the
fullest. So I do not know if Knapsack solutions would specifically
apply to this situation.

I know that you said it should lead me in the right direction, but I
am not sure how to apply the Knapsack problem to this problem.

Thanks

-Jeff
From: Mensanator on 30 Jun 2008 18:56
On Jun 30, 12:38 pm, jeffbg123 <jeffbg...(a)gmail.com> wrote:
> Hey,
>
> I am trying to figure out the quickest way to do the following.
>
> You are given a list of integers, a goal sum (integer), and an
> acceptable +/- (integer).
>
> The goal is to find a list of integers, all from the first list (all
> unique) that sum up to the goal sum plus or minus the acceptable
> range.
>
> Example:
>
> list: 1,2,3,4,5,6,7,8,9
> Goal: 8
> +/-: 1
>
> It would output one of the following, whichever it found first:
> 1,2,4
> 1,3,4
> 1,6
> 1,7
> .......etc
>
> Basically whatever numbers sum to 7,8, or 9
>
> Make sense?
>
> Is there a quick way of doing this? Notably faster than brute force?

Sure, if you use brute force intelligently:

check all combinations taken 1,2,3,...n at a time

# Python
#
# Calculate Permutations (with/without replacement)
# Combinations (with/without replacement)

def ooloop6(a, n, perm=True, repl=True):
if (not repl) and (n>len(a)): return
r0 = range(n)
r1 = r0[1:]
if perm and repl: # ok m**n
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
e = ''.join(["p = [' '.join((",v,")) ",f,"]"])
exec e
return p
if (not perm) and repl: # ok (m+n-1)!/(n!
(m-1)!)
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join(['(c%s>=c%s)' % (j,j-1) for j in r1])
e = ''.join(["p = [' '.join((",v,")) ",f," if ",i,"]"])
exec e
return p
if perm and (not repl): # ok m!/(m-n)!
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join([' and '.join(['(c%s!=c%s)' % (j,k) for k in
range(j)]) for j in r1])
e = ''.join(["p = [' '.join((",v,")) ",f," if ",i,"]"])
exec e
return p
if (not perm) and (not repl): # ok m!/(n!(m-n)!)
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join(['(c%s>c%s)' % (j,j-1) for j in r1])
e = ''.join(["p = [' '.join((",v,")) ",f," if ",i,"]"])
exec e
#print '\n\n',e,'\n\n'
return p

a = '1 2 3 4 5 6 7 8 9'.split() # list assumed to be sorted

listsumrange = range(7,10)

running_sum = 0
running_count = 0
for k in a: # combinations taken 1 at a time
s = int(k)
running_sum += s
if running_sum <= listsumrange[-1]: # don't check neddlessly
running_count += 1
if s in listsumrange:
print k

for n in xrange(2,running_count+1): # combinations taken n at a time
p = ooloop6(a,n,False,False)
pp = [[int(j) for j in i.split()] for i in p]
for k in pp:
if sum(k) in listsumrange:
print k

----------------------------------------------------------

For listsumrange = range(7,10):

7
8
9
[1, 6]
[1, 7]
[1, 8]
[2, 5]
[2, 6]
[2, 7]
[3, 4]
[3, 5]
[3, 6]
[4, 5]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[2, 3, 4]

Note, for 4 at a time, smallest combination [1,2,3,4]
exceeds listsumrange, so no point in checking higher combos.

For listsumrange = range(7,13):

7
8
9
[1, 6]
[1, 7]
[1, 8]
[1, 9]
[2, 5]
[2, 6]
[2, 7]
[2, 8]
[2, 9]
[3, 4]
[3, 5]
[3, 6]
[3, 7]
[3, 8]
[3, 9]
[4, 5]
[4, 6]
[4, 7]
[4, 8]
[5, 6]
[5, 7]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 2, 7]
[1, 2, 8]
[1, 2, 9]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 3, 7]
[1, 3, 8]
[1, 4, 5]
[1, 4, 6]
[1, 4, 7]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 3, 7]
[2, 4, 5]
[2, 4, 6]
[3, 4, 5]
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 4, 5]
From: Gene on 30 Jun 2008 19:46
On Jun 30, 3:20 pm, jeffbg123 <jeffbg...(a)gmail.com> wrote:
> Thanks for the advice Paul.
>
> I am hesitant to accept solutions that are efficient for the knapsack
> problem as I would suspect it would be an easier solution when all of
> the values of the items are exactly the same. You do not gain anything
> from adding the largest item over the smallest item. And you are not
> going for the most songs, you are going to try to get the knapsack the
> fullest. So I do not know if Knapsack solutions would specifically
> apply to this situation.
>
> I know that you said it should lead me in the right direction, but I
> am not sure how to apply the Knapsack problem to this problem.
>
> Thanks
>
> -Jeff

The better reference is the "subset sum" problem. There is a semi-
efficient dynamic programming solution. It's run time is polynomial,
but it depends on the magnitude of the set elements and the target.
 |  Next  |  Last
Pages: 1 2
Prev: Chopard Mille Miglia GMT Chronograph Mens Watch 16/8992/3
Next: Sorting of Base64 strings