We discussed the fractional Knapsack problem in class as a problem solvable by a
ID: 3825213 • Letter: W
Question
We discussed the fractional Knapsack problem in class as a problem solvable by a greedy algorithm. However, the 0-1 Knapsack problem was not solvable by a Greedy algorithm but it is solvable through dynamic programming.
(a)To apply dynamic programing the problem needs to have sub optimality. Proof that the 0-1 Knapsack problem has sub-optimality.
(b) Develop a recursive strategy to solve the 0-1 Knapsack problem leveraging the sub –optimality property shown in (a).
(c)Develop a bottom up dynamic programing method to solve the 0-1 Knapsack problem.
(d)Compare the computational complexity between the recursive and the dynamic programing solution.
Explanation / Answer
a)
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
b)
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}
c)
// 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] = 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];
}
d)
Time Complexity of dynamic approach: O(nW) where n is the number of items and W is the capacity of knapsack
Time complexity of recursive solution is O(2^n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.