« Benford's Law, Zipf's Law and the Pareto Distribution | Main | Thoughts on UseR! 2009 »

July 10, 2009

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a010534b1db25970b0115705ca0e9970c

Listed below are links to weblogs that reference Because it's Friday: The Knapsack Problem:

Comments

Feed You can follow this conversation by subscribing to the comment feed for this post.

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

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....

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?

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

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

The comments to this entry are closed.


R for the Enterprise

Got comments or suggestions for the blog editor?
Email David Smith.
Follow revodavid on Twitter Follow David on Twitter: @revodavid

Search Revolutions Blog