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.