# subsetsum: Subset Sum Problem In adagio: Discrete and Global Optimization Routines

## Description

Subset sum routine for positive integers.

## Usage

 `1` ```subsetsum(S, t, method = "greedy") ```

## Arguments

 `S` vector of positive integers. `t` target value. `method` can be “greedy” or “dynamic”, where “dynamic” stands for the dynamic programming approach.

## Details

Searching for a set of elements in `S` that sum up to `t` by continuously adding more elements of `S`.

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.

The dynamic method may be faster for large sets, but will also require much more memory if the target value is large.

## Value

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.

## Note

Will be replaced by a compiled version.

## Author(s)

HwB email: <[email protected]>

## References

Horowitz, E., and S. Sahni (1978). Fundamentals of Computer Algorithms. Computer Science Press, Rockville, ML.

`maxsub`
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28``` ```## 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.320 0.032 0.359 prods[is] # [1] 70740 70740 71190 76950 77382 80000 83800 # [8] 90900 456000 533600 829350 1110000 1198000 sum(prods[is]) == amount # [1] TRUE ## End(Not run) ```