subsetsum {adagio} | R Documentation |

Subset sum routine for positive integers.

subsetsum(S, t, method = "greedy") sss_test(S, t)

`S` |
vector of positive integers. |

`t` |
target value, bigger than all items in |

`method` |
can be “greedy” or “dynamic”, where “dynamic” stands for the dynamic programming approach. |

`subsetsum`

is searching for a set of elements in `S`

that
sum up to `t`

by continuously adding more elements of `S`

.

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 `t`

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 `S`

to be sorted decreasingly, too.

List with the target value, if reached, and vector of indices of elements
in `S`

that sum up to `t`

.

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 `subsetsum`

.
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: <hwborchers@googlemail.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] # [1] 70740 70740 71190 76950 77382 80000 83800 # [8] 90900 456000 533600 829350 1110000 1198000 sum(prods[is]) == amount # [1] 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)

[Package *adagio* version 0.8.4 Index]