Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSI 2120 Programming Paradigm
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
< ?0,?1,?2,…,??−1 > and < ?0,?1,?2,…,??−1 >
and a number W > 0, find the subset K ⸦ {0,1,…,n-1} that maximizes
subject to
∑?? ?∊?
∑?? ≤? ?∊?
Example:
Consider the following example with a knapsack of capacity 7:
The solution to this problem is to select items B and D for a total value of 21 and a total weight of 7.
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.
Item A |
Item B Item C Item D |
|||
Value |
1 |
6 |
10 |
15 |
Weight |
1 |
2 |
3 |
5 |
Few observations about the knapsack solution tree:
number of items becomes large.
We therefore need a better algorithm to solve this problem in the general case.