Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

David posts a question about how to solve this knapsack problem using the R statistical computing and analysis platform. My reply in the comments seems to have disappeared for a while so here is my proposed solution. See David’s blog for my earlier proposed solution with a very common error.

## http://blog.revolution-computing.com/2009/07/because-its-friday-the-knapsack-problem.html
appetizer.solution <- local (
function (target) {
app <- c(2.15, 2.75, 3.35, 3.55, 4.20, 5.80)
r <- 2L
repeat {
c <- gtools::combinations(length(app), r=r, v=app, repeats.allowed=TRUE)
s <- rowSums(c)
if ( all(s > target) ) {
print("No solution found")
break
}
x <- which( abs(s-target) < 1e-4 )
if ( length(x) > 0L ) {
cat("Solution found: ", c[x,], "\n")
break
}
r <- r + 1L
}
})

appetizer.solution(15.05)
# Solution found:  2.15 3.55 3.55 5.8


Brute force works, it just doesn’t scale well. (Note that 7×2.15 is another solution.)