[R] Subset sum problem.

[Geert Janssens]

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
>