0-1 Knapsack Problem
Reading time: 20 minutes | Coding time: 10 minutes
Given n
items, in which the i
th item has weight wi
and value vi
, find the maximum total value that can be put in a knapsack of capacity W
. You cannot break an item, either pick the complete item, or don't pick it.
Solution
We first start by building a table consisting of rows of values and columns of weights.
Starting from the first row and column, we keep on filling the table till the desired value is obtained.
Let the table be represented as $dp[n, w]$ where $n$ is the number of items to be included and $w$ is the left over space in the bag.
For every object, there can be two possibilities:
- if the object's weight is greater than the leftover space in the bag,
then $dp[n, w]$ = $dp[n - 1, w]$ - else,
the object might be taken or left out.- if it is taken, the total value of the bag becomes $dp[n, w]$ = $vn$ + $dp[n - , w - wn]$, where
vn
is value of the $n$th object and $wn$ is its weight. - if the object is not included, $dp[n, w]$ = $dp[n - 1, w]$
- if it is taken, the total value of the bag becomes $dp[n, w]$ = $vn$ + $dp[n - , w - wn]$, where
The value of $dp[n,w]$ is the maximum of both these cases.
In short, the optimal substructure to compute $dp[n, w]$ is:
dp[n, w] = dp[n-1, w], if wn > w
= max( dp[n-1, w], vn + dp[n-1, w - wn] ), otherwise
Complexity
- Time complexity:
Θ(n*W)
- Space complexity:
Θ(n*W)
Implementation
- Java
Java
import java.util.Scanner;
import java.lang.Math;
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int W = s.nextInt();
int val[] = new int[n];
int weight[] = new int[n];
for(int i = 0;i<n;i++) val[i] = s.nextInt();
for(int i = 0;i<n;i++) weight[i] = s.nextInt();
int dp[][] = new int[n+1][W+1];
for(int i = 0;i<=n;i++) {
for(int w = 0;w<=W;w++) {
if(i==0||w==0) continue;
if(weight[i-1]>w) dp[i][w] = dp[i-1][w];
else dp[i][w] = Math.max(val[i-1]+dp[i-1][w-weight[i-1]], dp[i-1][w]);
}
}
System.out.println(dp[n][W]);
}
}
Example
Input:
4
7
1 4 5 7
1 3 4 5
Output:
9
for this input, the final dp
array will be constructed as
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
3 | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
4 | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
here, the rows 1,2,3,4 correspond to items (val)weight - (1)1, (4)3, (5)4, (7)5 respectively and the columns 0,1,2...7 correspond to remaining weight in the bag.