DP algorithm for bounded Knapsack?

algorithm knapsack-problem
lithuak picture lithuak · Mar 5, 2012 · Viewed 11.5k times · Source

The Wikipedia article about Knapsack problem contains lists three kinds of it:

  1. 1-0 (one item of a type)

  2. Bounded (several items of a type)

  3. Unbounded (unlimited number of items of a type)

The article contains DP approaches for 1. and 3. types of problem, but no solution for 2.

How can the dynamic programming algorithm for solving 2. be described?

Answer

Irit Katriel picture Irit Katriel · Mar 5, 2012

Use the 0-1 variant, but allow repetition of an item in the solution up to the number of times specified in its bound. You would need to maintain a vector stating how many copies of each item you already included in the partial solution.

Related questions

How do I solve the 'classic' knapsack algorithm recursively?

This is my task The Knapsack Problem is a classic in computer science. In its simplest form it involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. …

Read More
Multiple Constraint Knapsack Problem

If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply-constrained knapsack problem, multi-dimensional knapsack problem, or m-dimensional knapsack …

Read More
Solving the Integer Knapsack

I a new to dynamic programing and have tried the integer knapsack problem here at SPOJ (http://www.spoj.pl/problems/KNAPSACK/) . However, for the given test cases my solution is not giving the correct output. I'd be thankful to …

Read More