Geert Janssens <janssens-geert <at> telenet.be> writes: > > Hi, > > I'm quite new to the R-project. I was suggested to look into it because I am > trying to solve the "Subset sum" problem", which basically is: > Given a set of integers and an integer s, does any non-empty subset sum to s? > (See http://en.wikipedia.org/wiki/Subset_sum_problem) > > I have been searching the web for quite some time now (which is how I > eventually discovered that my problem is called subset sum), but I can't seem > to find an easily applicable implementation. I did search the list archive, > the R website and used the help.search and apropos function. I'm afraid > nothing obvious showed up for me. > > 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"): # Exact algorithm for the SUBSET SUM problem exactSubsetSum <- function(S, t) { S <- S[S <= t] if (sum(S) < t) return(FALSE) S <- sort(S, decreasing=TRUE) n <- length(S) L <- c(0) for (i in 1:n) { L <- unique(sort(c(L, L + S[i]))) L <- L[L <= t] if (max(L) == t) return(TRUE) } return(FALSE) } # Example with a set of cardinality 64 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) # Timing is not that bad system.time( sol <- exactSubsetSum(products, amount) ) # user system elapsed # 0.516 0.096 0.673 sol # [1] TRUE > Thank you very much. > > Geert > ______________________________________________ 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.