Knapsack Problems
- The 0/1 Knapsack Problem
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0–1 property) (https://www.geeksforgeeks.org/knapsack-problem/)
Another way to phrase this question is: “Imagine you have a homework assignment with different parts labeled A through G. Each part has a “value” (in points) and a “size” (time in hours to complete). For example, say the values and times for our assignment are:
Say you have a total of 15 hours: which parts should you do?” (https://www.cs.cmu.edu/~avrim/451f09/lectures/lect1001.pdf)
Recurrence relation: R(n, W) = max(val[n] + R(n -1, W-wt[n]), R(n-1, W))
We can look at this in the perspective of trying to solve questions that would maximize my total grade. Solving a problem results in a different set of problems to choose from as opposed to not solving the problem. If we solve the problem, we should move onto solving the next problem after adding the value of the problem and taking the hours spent on the problem from the total time. If we don’t solve the problem, the total time does not change, but we can move onto solving the next problem. Therefore, we need to choose maximum out of those two.
Another way of looking at this problem is using weights and knapsack. If I want to add an item to my knapsack, I need to start with a smaller size of my knapsack first. I can start with 1. Since I can add only one item, I will look at it item by item. To add the current item, I would need to look at what is the maximum value without adding the current item, and adding the current item with the weight after subtracting the weight of current item. Once I decided that not adding that item and taking something out of my backpack is better since what I had originally has more values, that item will not be looked at again. The overlapping subproblems are that when considering to add an item, I need to take what’s inside my backpack (If my backpack is big enough, in this case, I am taking 0 weight out of my backpack) or I carry on with whatever I had previously without adding the new item. So, n-1 is for 0–1 knapsack problem that guarantees that items will be taken into consideration one by one. Once the item is not added, it won’t be looked at again.
Bottom-up solution:
Since there are two variables, two-dimensional solution would do. The rows can represent the items. The problem is the column, because the resultant weight, after the subtraction, if the problem is chosen to be solved, available weights vary. Therefore, we will make the column every weight possible, which is 0 to the total weight.
And the next problem is how should we fill up the matrix?
Running time: Note that it really depends on the size of weight. So the running time is O(nW) where n is the number of items. Here, W can be extremely large and it can increase its size exponentially as opposed to polynomially, although W looks polynomial in a small sample. Therefore, the algorithm has a pseudo-polynomial running time.
2. Unbounded Knapsack Problem
Given a knapsack weight W and a set of n items with certain value val[i] and weight wt[i], we need to calculate minimum amount that could make up this quantity exactly (https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/).
Recurrence relation: R(W) = max { val + R(W — w), R(W)) or
R(W) = max { val + R(W — w)} when t goes from 0 to w
This problem has unlimited number of each item, so the item value does not have to change for each iteration. Therefore, only one variable is sufficient.
Bottom up solution:
- one variable == 1 dimensional array
Since there is only one variable, one dimensional array can represent the solution.
2. unpredictable outcomes after the subtraction of weight
It means elements of the one dimensional array have to represent all possible values of the weight: 0, 1, 2, …, W
3. repretition == k loop
For each element of the array, all possible options of k items need to be considered.
4. linear recursion expression
It means intermediate values of the k loop is saved in the same array.
R(W) = max { val + R(W — w), R(W))
R(W) = max { val + R(W — w)}
is the same recurrence relation as the one mentioned above.
We will have one dimensional array but for each iteration of the array, there will be j iteration that compares the options we have.
Running time: Nk
3. Fractional Knapsack Problem
In 0–1 knapsack problem, it’s either we put the item or we don’t, instead of putting a fraction of it. In fractional knapsack problem, we can break items for maximizing the total value of knapsack (https://www.geeksforgeeks.org/fractional-knapsack-problem/).
Optimal solution: In order to solve this problem, a greedy approach can be made to get the optimal solution. It would take way too long to try to solve this problem like other dynamic programming approach. The basic idea is to calculate the ratio of value and weight for every item and sort them in the descending order: the higher the ratio, the earlier in the line. Then run a for loop to the sorted items to add items starting from the highest ratio until no item as a whole can be added.
Running time: It takes O(NlogN) to sort the items and O(N)to go through the sorted list. Therefore, it takes O(NlogN).
