Approximating 0-1 Knapsack.
Recall the 0-1 knapsack problem where
you are tasked with selecting items from a list of size n where each item i has weight Wi and
value v; but you an either choose to select the entire item or not (no fractional choices).
Assume that the list of items are sorted from largest to smallest value. The problem is
NP-hard, so we will try to approximate it with a ratio of 2.
Given an instance I of the 0-1 knapsack problem, let P be the optimal solution of I and let Q
be the optimal solution to fractional variant of I where a fraction of items can be selected.
As we have seen in class, Q will contain at most one item that is partially selected (the
others are either entirely selected or not at all). Let R be the set of items in Q but without
the fractionally chosen item. If V(S) denotes the value of a solution S, prove that:
V(R) > V(Q)/2 > V(P)/2
How does this analysis help you in designing an algorithm for finding an approximation to
instance I?
Answers
Answer:
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 items such that sum of the weights of those items of given 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).
Prerequisite : 0/1 Knapsack
Examples :
Input : val[] = {60, 100, 120};
wt[] = {10, 20, 30};
W = 50;
Output : 220 //maximum value that can be obtained
30 20 //weights 20 and 30 are included.
Input : val[] = {40, 100, 50, 60};
wt[] = {20, 10, 40, 30};
W = 60;
Output : 200
30 20 10
Approach :
Let val[] = {1, 4, 5, 7}, wt[] = {1, 3, 4, 5}
W = 7.
The 2d knapsack table will look like :
2d knapsack table
Start backtracking from K[n][W].Here K[n][W] is 9.
Since, this value comes from the top (shown by grey arrow), the item in this row is not included. Go vertically upward in the table without including this in the knapsack. Now, this value K[n-1][W] which is 9 doesn’t come from the top which means the item in this row is included and go vertically up and then left by the weight of the included item ( shown by black arrow). Continuing this process include weights 3 and 4 with total value 9 in the knapsack.
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
// CPP code for Dynamic Programming based
// solution for 0-1 Knapsack problem
#include <bits/stdc++.h>
// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Prints the items which are put in a knapsack of capacity W
void printknapSack(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];
}
}
// stores the result of Knapsack
int res = K[n][W];
printf("%d\n", res);
w = W;
for (i = n; i > 0 && res > 0; i--) {
// either the result comes from the top
// (K[i-1][w]) or from (val[i-1] + K[i-1]
// [w-wt[i-1]]) as in Knapsack table. If
// it comes from the latter one/ it means
// the item is included.
if (res == K[i - 1][w])
continue;
else {
// This item is included.
printf("%d ", wt[i - 1]);
// Since this weight is included its
// value is deducted
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
// Driver code
int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0