Because it's Friday: The Knapsack Problem

A particularly geeky strip from XKCD:

Any suggestions on how one might solve this problem in R?

XKCD: NP-Complete

Comments

[Allan Engelhardt]

Brute force works for me:

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( s == target )
	if ( length(x) > 0L ) {
	  print("Solution found")
	  print(c[x,])
	  break
	}
	r <- r + 1L
  }
})
appetizer.solution(15.05)
# [1] "No solution found"
appetizer.solution(15.15)
# [1] "Solution found"
#      [,1] [,2] [,3] [,4] [,5]
# [1,] 2.15 2.75 3.35 3.35 3.55
# [2,] 2.75 2.75 2.75 3.35 3.55

[Allan Engelhardt]

I can’t believe I just wrote that. Must be the heat. This must be the most elementary mistake in numerical analysis. Try this version instead:

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 ) {
	  print("Solution found")
	  print(c[x,])
	  break
	}
	r <- r + 1L
  }
})
appetizer.solution(15.05)
# [1] "Solution found"
# [1] 3.55 5.80 5.80

I'll go and kill myself now....

[Chris P]

Wait a minute, if repeats are allowed, then you have to have different utilities for second replicate. Decreasing marginal returns. Where are you getting your item utilities from?

[Stephen Le Guen]

A marginally better solution exists by reducing the problem 'dynamically.' I have implemented this as a program for the subset sum problem but this versio n assumed repetitions are not allowed. An adaptation to allow repeats should still work.

The program and a pdf version of a flowchart for it are available at;
www.cybase.co.uk/wlcs/Software.html

[Stephen Le Guen]

Looking at the answer given by Allan the solution is incorrect!

3.55 + 5.80 + 5.80 = 15.15

Also the answer above totals 15.15, but the original problem found no solution only as 15.15, he apparently tried again with the second target sum.

My program does not search for solutions with duplicates, but allows duplicate alues to be entered. Doubling up eaxh entry finds the solution

2.15 + 3.55 + 3.55 + 5.80 = 15.05

but the values are entered as whole numbers.

Steve