The Knapsack Problem
Want to share your content on Rbloggers? 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.revolutioncomputing.com/2009/07/becauseitsfridaytheknapsackproblem.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(starget) < 1e4 ) 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.)
Jump to comments.
You may also like these posts:

Employee productivity as function of number of workers revisited
We have a mild obsession with employee productivity and how that declines as companies get bigger. We have previously found that when you treble the number of workers, you halve their individual productivity which is mildly scary. We revisit the analysis …
Rbloggers.com offers daily email updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/datascience job.
Want to share your content on Rbloggers? click here if you have a blog, or here if you don't.