Description Usage Arguments Details Value Note Author(s) References See Also Examples

Subset sum routine for positive integers.

1 |

`S` |
vector of positive integers. |

`t` |
target value. |

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

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.

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.

Will be replaced by a compiled version.

HwB email: <[email protected]>

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

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

adagio documentation built on May 17, 2018, 3:01 a.m.

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.