[R] Subset sum problem.

[Geert Janssens]

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 at 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.