Algorithms For Dummies

  Relying on Dynamic Programming 

     309

This section shows how to solve the 1-0 knapsack problem. In this case, you have a 

finite number of items and can put each of them into the knapsack (the one sta-

tus) or not (the zero status). It’s useful to know there are other possible variants 

of the problem:

 

»

Fractional knapsack problem: Deals with quantities. For example, an item 

could be kilograms of flour, and you must pick the best quantity. You can 

solve this version using a greedy algorithm.

 

»

Bounded knapsack problem: Puts one or more copies of the same item into 

the knapsack. In this case, you must deal with minimum and maximum 

number requirements for each item you pick.

 

»

Unbounded knapsack problem: Puts one or more copies of the same item 

into the knapsack without constraints. The only limit is that you can’t put a 

negative number of items into the knapsack.

The 1-0 knapsack problem relies on a dynamic programming solution and runs in 

pseudo-polynomial time (which is worse than just polynomial time) because the 

running time depends on the number of items (n) multiplied by the number of 

fractions of the knapsack capacity (W) that you use on building your partial solu-

tion. When using big-O notation, you can say that the running time is 

O(nW)

. The 

brute-force version of the algorithm instead runs in 

O(2

n

)

. The algorithm works 

like this:

1. 

Given the knapsack capacity, test a range of smaller knapsacks (subproblems). 

In this case, given a knapsack capable of carrying 20 kilograms, the algorithm 

tests a range of knapsacks carrying from 0 kilograms to 20 kilograms.

2. 

For each item, test how it fits in each of the knapsacks, from the smallest 

knapsack to the largest. At each test, if the item can fit, choose the best value 

from the following:

a.  The solution offered by the previous smaller knapsack

b.  The test item, plus you fill the residual space with the best valued solution 

previously that filled that space

The code runs the knapsack algorithm and solves the problem with a set of six 

items of different weight and value combinations as well as a 20-kg knapsack:

Item

1

2

3

4

5

6

Weight in kg

2

3

4

4

5

9

Profit in 100 USD

3

4

3

5

8

10

---

310

 

   

  PART 5