2. 0–1 Knapsack Problem

In 0–1 Knapsack problem, we are given a set of items, each with a weight and a value and we need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Please note that the items are indivisible; we can either take an item or not (0–1 property). For example,

Input:
value = [ 20, 5, 10, 40, 15, 25 ]
weight = [ 1, 2, 3, 8, 7, 4 ]
int W = 10

Output: Knapsack value is 60

value = 20 + 40 = 60
weight = 1 + 8 = 9 < W

The idea is to use recursion to solve this problem. For each item, there are two possibilities –

1. We include current item in knapSack and recur for remaining items with decreased capacity of Knapsack. If the capacity becomes negative, do not recur or return -INFINITY.
2. We exclude current item from knapSack and recur for remaining items.

Finally, we return maximum value we get by including or excluding current item. The base case of the recursion would be when no items are left or capacity becomes 0.

class Main
{
 public static int knapSack(int[] v, int[] w, int n, int W)
 {
 if (W < 0) {
 return Integer.MIN_VALUE;
 }
 if (n < 0 || W == 0) {
 return 0;
 }
 int include = v[n] + knapSack(v, w, n — 1, W — w[n]);
 int exclude = knapSack(v, w, n — 1, W);
 return Integer.max(include, exclude);
}
 public static void main(String[] args)
 {
 int[] v = { 20, 5, 10, 40, 15, 25 };
 int[] w = { 1, 2, 3, 8, 7, 4 };
 int W = 10;
System.out.println(“Knapsack value is “ +
 knapSack(v, w, v.length — 1, W));
 }
}

The above solution has an optimal substructure i.e. optimal solution can be constructed efficiently from optimal solutions of its subproblems. It also has overlapping subproblems i.e. the problem can be broken down into subproblems which are reused several times. In order to reuse subproblems solutions, we can apply Dynamic Programming, in which subproblem solutions are Memoized rather than computed over and over again. Below Memoized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

import java.util.HashMap;
import java.util.Map;
class Main
{

 public static int knapSack(int[] v, int[] w, int n, int W,
 Map<String, Integer> lookup)
 {
 if (W < 0) {
 return Integer.MIN_VALUE;
 }
 if (n < 0 || W == 0) {
 return 0;
 }
 String key = n + “|” + W;
 if (!lookup.containsKey(key))
 {

 int include = v[n] + knapSack(v, w, n — 1, W — w[n], lookup);
 int exclude = knapSack(v, w, n — 1, W, lookup);
 lookup.put(key, Integer.max(include, exclude));
 }
 return lookup.get(key);
 }
 public static void main(String[] args)
 {
 int[] v = { 20, 5, 10, 40, 15, 25 };
 int[] w = { 1, 2, 3, 8, 7, 4 };
 int W = 10;
 Map<String, Integer> lookup = new HashMap<>();
System.out.println(“Knapsack value is “ +
 knapSack(v, w, v.length — 1, W, lookup));
 }
}

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes T[i][j], for each 1 <= i <= n and 0 <= j <= W, which is maximum value that can be attained with weight less than or equal to j and using items up to first i items. It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.

class Main
{

 public static int knapSack(int[] v, int[] w, int W)
 {

  int[][] T = new int[v.length + 1][W + 1];
  for (int i = 1; i <= v.length; i++)
  {
   for (int j = 0; j <= W; j++)
   {
    if (w[i-1] > j) {
     T[i][j] = T[i-1][j];
    }
    else {
     T[i][j] = Integer.max(T[i-1][j],
       T[i-1][j-w[i-1]] + v[i-1]);
    }
   }
  }
  return T[v.length][W];
 }
public static void main(String[] args)
 {
  int[] v = { 20, 5, 10, 40, 15, 25 };
  int[] w = {  1, 2,  3,  8,  7, 4 };
  int W = 10;
System.out.println("Knapsack value is "
    + knapSack(v, w, W));
 }
}