Hans, you're my personal hero today !
The function seems to work fine for the tests I did already.
Thank you very much !
Geert
On Thursday 10 December 2009, Hans W Borchers wrote:
> Geert Janssens <janssens-geert <at> telenet.be> writes:
> > On Wednesday 9 December 2009, Hans W Borchers wrote:
> > > Geert Janssens <janssens-geert <at> telenet.be> writes:
> > > > [ ... ]
> > > > Has anybody tackled this issue before in R ? If so, I would be very
> > > > grateful if you could share your solution with me.
> > >
> > > Is it really true that you only want to see a "Yes or No" answer to
> > > this question whether a subset sums up to s --- without learning which
> > > numbers this subset is composed of (the pure SUBSET SUM problem)?
> > > Then the following procedure does that in a reasonable amount of time
> > > (returning 'TRUE' or 'FALSE' instead of "Y-or-N"):
> >
> > Unfortunately no. I do need the numbers in the subset. But thank you for
> > presenting this code.
> >
> > Geert
>
> Okay then, here we go. But don't tell later that your requirement was to
> generate _all_ subsets that add up to a certain amount. I will generate
> only one (with largest elements).
>
> For simplicity I assume that the set is prepared s.t. it is decreasingly
> ordered, has no elements larger than the amount given, and has a total sum
> larger than this amount.
>
> # Assume S decreasing, no elements > t, total sum >= t
> solveSubsetSum <- function(S, t) {
> L <- c(0)
> inds <- NULL
> for (i in 1:length(S)) {
> # L <- unique(sort(c(L, L + S[i])))
> L <- c(L, L+S[i])
> L <- L[L <= t]
> if (max(L) == t) {
> inds <- c(i)
> t <- t - S[i]
> while (t > 0) {
> K <- c(0)
> for (j in 1:(i-1)) {
> K <- c(K, K+S[j])
> if (t %in% K) break
> }
> inds <- c(inds, j)
> t <- t - S[j]
> }
> break
> }
> }
> return(inds)
> }
>
> # former example
> 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 <- solveSubsetSum(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
>
> Note that running times and memory needs will be much higher when more
> summands are needed. To mention that too: I have not tested the code
> extensively.
>
> Regards
> Hans Werner
>
> ______________________________________________
> R-help@r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html and provide commented, minimal,
> self-contained, reproducible code.
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
