Knapsack problem with specified number of weights can be used

1
votes

I have a knapsack problem with specified knapsack capacity for weight and weights count.

I need an algorithm that packs weights to knapsack when knapsack capacity is C, needed weights count is N and there is a list of weights. Sorting of weights doesn't matter. It would be best if algorithm is recursive.

For example:
I have knapsack witch can hold only 3 weights and they have to weight 10 and I have these weights: 9, 8, 7, 2, 1. The correct (and only) answer is 7, 2, 1.

It would be best if someone write pseudocode, but its ok if its any of the common programing languages.

P.S. Any tips its appreciated as well :)

[EDIT]I need algorithm that gives answer with exactly the N weights count which weights exactly C.

2
recursionpseudocodeknapsack-problem

2 Answers

1
votes

This is the 0-1 knapsack problem, which can be solved using dynamic programming in pseudo-plynomial time.

See Wikipedia's knapsack problem article for instructions on how to solve the problem using dynamic programming.

See these CS lecture slides for a walk-through and pseudocode.

0
votes

http://en.wikipedia.org/wiki/Knapsack_problem should help you. They have pseudocode for algorithms as well.