The Knapsack Problem

July 10, 2009

(This article was first published on CYBAEA Data and Analysis, and kindly contributed to R-bloggers)

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.

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")
	x <- which( abs(s-target) < 1e-4 )
	if ( length(x) > 0L ) {
	  cat("Solution found: ", c[x,], "\n")
	r <- r + 1L

# 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:

  1. [0.38]
    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 …

To leave a comment for the author, please follow the link and comment on their blog: CYBAEA Data and Analysis. offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)