Subset sum routine for positive integers.
subsetsum(S, t, method = "greedy") sss_test(S, t)
vector of positive integers.
target value, bigger than all items in
can be “greedy” or “dynamic”, where “dynamic” stands for the dynamic programming approach.
subsetsum is searching for a set of elements in
sum up to
t by continuously adding more elements of
It is not required that
S is decreasingly sorted. But for reasons
of efficiency and smaller execution times it is urgently recommended to
sort the item set in decreasing order. See the examples to find out how
to handle your data.
The first components will be preferred, i.e., if
S is decreasing,
the sum with larger elements will be found, if increasing, the sum with
smaller elements. Because of timing considerations, the default is to
sort decreasingly before processing.
The dynamic method may be faster for large sets, but will also require much more memory if the target value is large.
sss_test will find the biggest number below or equal to
that can be expressed as a sum of items in
S. It will not return
any indices. It can be quite fast, though it preprocesses the set
to be sorted decreasingly, too.
List with the target value, if reached, and vector of indices of elements
S that sum up to
If no solution is found, the dynamic method will return indices for the largest value below the target, the greedy method witll return NULL.
sss_test will simply return maximum sum value found.
A compiled version – and much faster, in Fortran – can be found in
package 'knapsack' (R-Forge, project 'optimist') as
A recursive version, returning *all* solutions, is much too slow in R,
but is possible in Julia and can be asked from the author.
HwB email: <email@example.com>
Horowitz, E., and S. Sahni (1978). Fundamentals of Computer Algorithms. Computer Science Press, Rockville, ML.
t <- 5842 S <- c(267, 493, 869, 961, 1000, 1153, 1246, 1598, 1766, 1922) # S is not decreasingly sorted, so ... o <- order(S, decreasing = TRUE) So <- S[o] # So is decreasingly sorted sol <- subsetsum(So, t) # $inds: 2 4 6 7 8 w.r.t. So is <- o[sol$inds] # is: 9 7 5 4 3 w.r.t. S sum(S[is]) # 5842 ## Not run: amount <- 4748652 products <- c(30500,30500,30500,30500,42000,42000,42000,42000, 42000,42000,42000,42000,42000,42000,71040,90900, 76950,35100,71190,53730,456000,70740,70740,533600, 83800,59500,27465,28000,28000,28000,28000,28000, 26140,49600,77000,123289,27000,27000,27000,27000, 27000,27000,80000,33000,33000,55000,77382,48048, 51186,40000,35000,21716,63051,15025,15025,15025, 15025,800000,1110000,59700,25908,829350,1198000,1031655) # prepare set prods <- products[products <= amount] # no elements > amount prods <- sort(prods, decreasing=TRUE) # decreasing order # now find one solution system.time(is <- subsetsum(prods, amount)) # user system elapsed # 0.030 0.000 0.029 prods[is] #  70740 70740 71190 76950 77382 80000 83800 #  90900 456000 533600 829350 1110000 1198000 sum(prods[is]) == amount #  TRUE # Timings: # unsorted decr.sorted # "greedy" 22.930 0.030 (therefore the default settings) # "dynamic" 2.515 0.860 (overhead for smaller sets) # sss_test 8.450 0.040 (no indices returned) ## End(Not run)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.