[R] Subset sum problem.

[Hans W Borchers]

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
>