The Knapsack Problem

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.

## because-its-friday-the-knapsack-problem
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.)