On Wednesday 9 December 2009, Hans W Borchers wrote:
> 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"):
>
Unfortunatly no. I do need the numbers in the subset. But thank you for
presenting this code.
Geert
> # 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
>
______________________________________________
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.
