[R] Subset sum problem.
Hans W Borchers
hwborchers at googlemail.com
Wed Dec 9 20:31:08 CET 2009
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
>
More information about the R-help
mailing list