Problem Statement 0-1 Knapsack problem
Input :
There are n items, and each item has a value:
Select a subset S ⊆ {1,2,3,....n}
There are two versions of problem:
Comparing Fractional Knapsack vs 0-1 Knapsack
Fractional knapsack problem
The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.
Exhibit greedy choice property.
0-1 knapsack problem
The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.
So, the above problem statement holds for 0-1 knapsack problem as we are referring to integral wi.
Since there are n items, there are 2^{n} possible combinations of items.
We go through all combinations and find the one with maximum value and with total weight less or equal to W
Running time will be O(2^{n})
Dynamic-Programming Solution to the 0-1 Knapsack Problem
The naive way to solve this problem is to cycle through all 2^{n} subsets of the n items and pick the subset with a legal weight that maximizes the value of the knapsack. But, we can find a dynamic programming algorithm that will USUALLY do better than this brute force technique.
Now lets see the dynamic programming route.
Input :
There are n items, and each item has a value:
- value vi (non negative)
- size or weight wi (non negative and integral )
- Capicity W (non negative and integer)
Select a subset S ⊆ {1,2,3,....n}
- that maximizes ∑ vi
- subject to max value&sum wi ≤ W
There are two versions of problem:
- Fractional knapsack problem
- 0-1 knapsack problem
Comparing Fractional Knapsack vs 0-1 Knapsack
Fractional knapsack problem
The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.
Exhibit greedy choice property.
- Greedy algorithm exists.
- Exhibit optimal substructure property.
0-1 knapsack problem
The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.
So, the above problem statement holds for 0-1 knapsack problem as we are referring to integral wi.
- Exhibit No greedy choice property. No greedy algorithm exists.
- Exhibit optimal substructure property.
- Only dynamic programming algorithm exists.
Since there are n items, there are 2^{n} possible combinations of items.
We go through all combinations and find the one with maximum value and with total weight less or equal to W
Running time will be O(2^{n})
Dynamic-Programming Solution to the 0-1 Knapsack Problem
The naive way to solve this problem is to cycle through all 2^{n} subsets of the n items and pick the subset with a legal weight that maximizes the value of the knapsack. But, we can find a dynamic programming algorithm that will USUALLY do better than this brute force technique.
Now lets see the dynamic programming route.
Let S be the optimal solution S.
Let n be the last item in an optimal solution S for W pounds.
Defining the sub problem - try 1
Let’s try this:
If items are labeled 1..n, then a subproblem would be to find an optimal solution for
Sk = {items labeled 1, 2, .. k}
If items are labeled 1..n, then a subproblem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k}
This is a reasonable subproblem definition.
The question is: can we describe the final solution (Sn ) in terms of subproblems (Sk)?
Unfortunately, we can’t do that.
Consider the following items:
n=5, W=20
Consider W= 20. Lets try to take 1st 4 items, ie. S4 and 1st 5 items - S5.
So, clearly S4 is not sub part of S5, hence our solution is flawed.
Defining the sub problem try 2
The subproblem then will be to compute V[i,x], i.e., to find an optimal solution for Sk = {items labeled 1, 2, .. i} in a knapsack of size x. Now we have to derive V[i,x].
Case 1: Suppose n ∉ S (n not in S)
Then S must be optimal solution with first n-1 Items Ii.
Maximum value obtained by n-1 items and W weight (excluding nth item).
Case2 : Suppose n ∈ S (n is indeed in S)
If we remove the last item n, then S - {n} is the optimal solution w.r.t. the 1st n-1 items and capacitiy W - wn.
Let V_{ix} = value of the best solution on that :
So, we have to keep track of how many items we have used and the total size.
for i ∈ {1,2,3,...n} and any x
V_{ix} = MAX ( V_{(i-1)x} , vi + V_{(i-1)}_{x- wi} ) OR
So, in case 1, wi>x. Item i can’t be part of the solution, since if it was, the total weight would be > w, which is unacceptable.
In case 2, wi ≤ x. Then the item i can be in the solution, and we choose the case with greater value.
One quick edge case, if wi > x, then we cant use it, and we have Vix = V(i-1)x , we are using case 1.
Step2 - The sub problem
Recall W and weight wi are integers, therefore in the worst case each case of residual capacities x ∈ {0,1,2,...,W).
Let A = 2-D array - as we have to keep track of 2 things - what items we have to use and what capacity we have to respect.
Running time
Note on run time: Clearly the run time of this algorithm is O(nW), based on the nested loop structure and the simple operation inside of both loops. When comparing this with the previous O(2^{n}), we find that depending on W, either the dynamic programming algorithm is more efficient or the brute force algorithm could be more efficient. (For example, for n=5, W=100000, brute force is preferable, but for n=30 and W=1000, the dynamic programming solution is preferable.)
Example
Lets take the example now.
Input:
n=4, W=5
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Solution
Lets denote sub problem solution weight by w, instead of x.
Case 0 - When we have no items, so w=0
case 1 - When we have w=0, so we have to select no items
After discussing the corner cases, lets now solve the actual problem.
Let n be the last item in an optimal solution S for W pounds.
Defining the sub problem - try 1
Let’s try this:
If items are labeled 1..n, then a subproblem would be to find an optimal solution for
Sk = {items labeled 1, 2, .. k}
If items are labeled 1..n, then a subproblem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k}
This is a reasonable subproblem definition.
The question is: can we describe the final solution (Sn ) in terms of subproblems (Sk)?
Unfortunately, we can’t do that.
Consider the following items:
n=5, W=20
i | Item | w_{i} | v_{i} or b_{i} |
1 |
I_{0} | 2 |
3 |
2 |
I_{1} | 4 |
5 |
3 |
I_{2} | 5 |
8 |
4 |
I_{3} | 3 |
4 |
5 |
I_{4} | 9 |
10 |
Consider W= 20. Lets try to take 1st 4 items, ie. S4 and 1st 5 items - S5.
So, clearly S4 is not sub part of S5, hence our solution is flawed.
Defining the sub problem try 2
The subproblem then will be to compute V[i,x], i.e., to find an optimal solution for Sk = {items labeled 1, 2, .. i} in a knapsack of size x. Now we have to derive V[i,x].
Case 1: Suppose n ∉ S (n not in S)
Then S must be optimal solution with first n-1 Items Ii.
Maximum value obtained by n-1 items and W weight (excluding nth item).
Case2 : Suppose n ∈ S (n is indeed in S)
If we remove the last item n, then S - {n} is the optimal solution w.r.t. the 1st n-1 items and capacitiy W - wn.
Let V_{ix} = value of the best solution on that :
- uses only the first i items
- has total size ≤ x
So, we have to keep track of how many items we have used and the total size.
for i ∈ {1,2,3,...n} and any x
V_{ix} = MAX ( V_{(i-1)x} , vi + V_{(i-1)}_{x- wi} ) OR
So, in case 1, wi>x. Item i can’t be part of the solution, since if it was, the total weight would be > w, which is unacceptable.
In case 2, wi ≤ x. Then the item i can be in the solution, and we choose the case with greater value.
One quick edge case, if wi > x, then we cant use it, and we have Vix = V(i-1)x , we are using case 1.
Step2 - The sub problem
Recall W and weight wi are integers, therefore in the worst case each case of residual capacities x ∈ {0,1,2,...,W).
Let A = 2-D array - as we have to keep track of 2 things - what items we have to use and what capacity we have to respect.
//The corner case where we don't take item at all, //i.e. i=0, and A[item,x] = 0 where item=0 for x = 0 to W A[0,x] = 0 FOR i=1 to n DO c[i, 0] = 0 FOR x=0 TO W A[i,x] = max ( A[i-1,x],A[i-1,x-wi]+vi )
Running time
Note on run time: Clearly the run time of this algorithm is O(nW), based on the nested loop structure and the simple operation inside of both loops. When comparing this with the previous O(2^{n}), we find that depending on W, either the dynamic programming algorithm is more efficient or the brute force algorithm could be more efficient. (For example, for n=5, W=100000, brute force is preferable, but for n=30 and W=1000, the dynamic programming solution is preferable.)
Example
Lets take the example now.
Input:
n=4, W=5
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Solution
Lets denote sub problem solution weight by w, instead of x.
Case 0 - When we have no items, so w=0
case 1 - When we have w=0, so we have to select no items
After discussing the corner cases, lets now solve the actual problem.
Knapsack in java
// Returns the maximum value that can be put in a knapsack of capacity W int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[n+1][W+1]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W]; } int main() { int val[] = {60, 100, 120}; int wt[] = {10, 20, 30}; int W = 50; int n = sizeof(val)/sizeof(val[0]); printf("%d", knapSack(W, wt, val, n)); return 0; }
Thanks
0 comments:
Post a Comment