[R] Subset sum problem.

[Hans W Borchers]

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