# Untitled

By: a guest on May 7th, 2012  |  syntax: None  |  size: 1.75 KB  |  hits: 10  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. Need algorithm (logic) for best sum combination from multi group list
2. findBest(groups, k):
3.   if (k < 0): return infinity //stop condition 1
4.   if (group is empty) return k //stop condition 2
5.   group <- groups.getFirst()
6.   min <- infinity
7.   best <- []
8.   for each element in group:
9.      (solValue,minResult) <- findBest(groups-group, k - element) //recursively check for solution, with decreasing number of groups, and modify k
10.      if (solValue < min):
11.         min <- solValue
12.         best <- minResult
13.         best.append((group,element)) //append the element we added to the solution
14.   //it is also possible to take no element from this group:
15.   (solValue,minResult) <- findBest(groups-grou, k - element)
16.   if (solValue < min):
17.      min <- solValue
18.      best <- minResult
19.   return (minResult,solValue)
20.
21. Sol(grp_i, S) = True      if(grp_i==1 && grp_i dataset has element S) // base case
22.               = True      if(Sol(grp_i-1, S)==True OR
23.                              there exists element 'e' in grp_i dataset
24.                              such that Sol(grp_i-1, S-e)==True)
25.               = False     otherwise
26.
27. def bestsum(data, maxsum):
28.   res = [0]*(maxsum+1)
29.   res[0] = []  # base case
30.   for group in data:
31.     new_res = list(res) # copy res
32.     for ele in group:
33.       for i in range(maxsum-ele+1):
34.         if res[i] != 0:
35.           new_res[i+ele] = list(res[i])
36.           new_res[i+ele].append(ele)
37.     res = new_res
38.   for i in range(maxsum, 0, -1):
39.     if res[i] != 0:
40.       return res[i]
41.       break
42.   return []
43.
44. print bestsum( [[2,3,5,10,15], [4,6,23,15,12], [23,34,12,1,5]], 25)
45. print bestsum( [[2,3,10,15],   [4,6,23,12],    [23,34,12,1]],   25)
46. print bestsum( [[3,10,15],     [4,6,12],       [23,34,12,1]],   25)
47.
48. ~\$ python2 subsetsum.py
49. [5, 15, 5]
50. [2, 23]
51. [12, 12]