Problem description
This comprehensive assignment asks you to solve the Knapsack problem using the programming
paradigm seen in class.
This problem can be expressed as follows: given a set of items, each of them having a weight and a
value and given a knapsack (i.e. a container for items) having a maximal weight capacity, find the
subset of items to be added to the knapsack that maximizes the total value without exceeding the weight
capacity. Each item can be inserted just once and cannot be subdivided. Note that we will solve here the
problem for which the item weights are expressed in integer units. Mathematically the problem to solve
is the following:
Given two sets of n positive integers
Solving the problem
There are two possible strategies to solve this problem: a brute-force solution and a dynamic
programming solution. We will ask you to compare both in this assignment.
1. Brute force
Here the idea is simply to consider all possible solutions and select the one giving the highest value.
Indeed, the solution space for this problem can be represented by a binary tree in which each level is
associated to a specific item. For each item, we have to take a binary decision: should we include it in the
knapsack or not? This binary decision is represented by the two branches below each node of the binary
tree.
For example, considering the case given in the table at the top of this page, we can first consider item A.
We have two options: if we add it to the knapsack, then we have a current value of 1 and a residual
capacity of 6 (because item A has a weight of 1 and our knapsack has a capacity of 7). Now, let’s consider
the next item, that is item B (this is the second level of our solution tree). The first node of this level
corresponds to the case where we already have item A in the knapsack. If we also choose to add item B
then the new value is 7 and the residual capacity is 4. If we do not add item B, then we still have current
value at 1 and capacity at 6. The second node of this level is for the case where we have not added item A
to the knapsack. In that case if we add item B, then we have a current value of 6 and a residual capacity
of 5. Finally, if we choose to not add these two items, our capacity is still at 7 and the value of this empty
knapsack is obviously at 0. The full solution tree is given on the next page, and the inspection of the tree
leaves gives us the best solution.