0-1 Knapsack Problem — Dynamic Programming

How to identify DP problems?

• Check keyword like maximise, minimise, largest, greatest, or optimal solution.

If you identify that the problem is solved by DP problem.

Firstly, try to solve that sort of problems using recursion.

In order to solve recursion we need to two things at least.

• Base condition
• Choice Diagram

How can you find the Base Condition?

When you are solving a problem using recursion, then you must have one recursion function.

That recursion function must have parameters.

For example in 0–1 knapsack problem

Parameters can be

• weight[] —
• profit[] -
• W — Weight of the array

Then thinks of smallest possible values of Parameters

for example

weight[] — The size of array can be reduced to zero(0). Though size of array is constant only, but if you processed one item, then size become n-1, once you processed second item, then size become n-2, like this size becomes 0 when you processed all the items of the array.

Similarly, profit[] size can be zero at some point.

W also become zero at some point. Because, if one item(with w1) processed, effective rest weight of bag is W-w1, once you processed 2nd item, W-w1-w2. At last W-w1-w2-…wn = 0

0-1 Knapsack Problem

Following problems can be solved by using 0–1 Knapsack

1. Subset Sum
2. Equal Sum Partition
3. Count of Subset Sum
4. Minimum Subset Sum
5. Target Sum
6. Subset sum of given difference

Problem 1 : 0–1 Knapsack Problem

GFG — https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

Given

• N items with weights(w1,w2,w3,….,wN) and profit(p1,p2,p3,…,pN) associated with it.
• A bag which can hold at max W weight.
• The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
• Output — sum of profit of items corresponding to the weights put into the bag

N = 3
wt[] = [4,5,1]
profit[] = [1,2,3]
W = 4
Output = 3

// Here, we can see Weight of bag is 4 

// So if we pick first item whose weight is 4, but profit associated with first it
// item is 1 only.

// 2nd item can not be put into the bag because its weight is 5 which is
// beyond bag capacity, hence we can't consider 2nd item.

// 3rd item's weight is 1 which is under max capacity of bag(5), the maximum
// profit we get once we put 3rd item into the bag.

Let’s see the implementation code in Java

package com.dynamicprogramming.knapsack;

import java.util.Arrays;

public class KnapSackDemo {

 static int[][] t;

 // Recursive approach
 static int knapsack(int[] wt, int[] profit, int w, int n) {
  if (n == 0 || w == 0) {
   return 0;
  }

  if (wt[n - 1] <= w) {
   // include or not include
   return Math.max(profit[n - 1] + knapsack(wt, profit, w - wt[n - 1], n - 1), knapsack(wt, profit, w, n - 1));
  }

  return knapsack(wt, profit, w, n - 1);
 }

 // Memoization Approach
 static int knapsackmemoized(int[] wt, int[] profit, int w, int n) {

  // Base case: if either index or remaining capacity is 0, return 0
  if (n == 0 || w == 0) {
   return 0;
  }

  if (t[n][w] != -1) {
   return t[n][w];
  }

  if (wt[n - 1] > w) {
   // If weight of current item exceeds remaining capacity, skip it
   return t[n][w] = knapsackmemoized(wt, profit, w, n - 1);
  }

  return t[n][w] = Math.max(profit[n - 1] + knapsackmemoized(wt, profit, w - wt[n - 1], n - 1),
    knapsackmemoized(wt, profit, w, n - 1));
 }

 // Top-Down Approach

 static int knapsacktopdown(int[] wt, int profit[], int w, int n) {

  int[][] t = new int[n + 1][w + 1];

  // Base condition - initialise first row and first column with 0
  for (int i = 0; i < n + 1; i++) {
   for (int j = 0; j < w + 1; j++) {
    if (i == 0 || j == 0) {
     t[i][j] = 0;
    }
   }
  }

  for (int i = 1; i < n + 1; i++) {
   for (int j = 1; j < w + 1; j++) {
    // Pay attention here, don't put w instead of j
    // Because we are comparing wt[i-1] with weight in the jth column not with whole
    // w(last column)
    if (wt[i - 1] > j) {
     t[i][j] = t[i - 1][j];
    } else {
     t[i][j] = Math.max(profit[i - 1] + t[i - 1][j - wt[i - 1]], t[i - 1][j]);
    }
   }
  }

  return t[n][w];
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub

  int[] wt = { 1, 3, 4, 5 };
  int[] profit = { 9, 4, 5, 6 };
  int capacity = 7;
  int n = wt.length;

  t = new int[n + 1][capacity + 1];

  for (int[] row : t) {
   Arrays.fill(row, -1);
  }

  System.out.println("Maximum value using Memoized Approach : " + knapsack(wt, profit, capacity, n));
  System.out.println("Maximum value using Memoized Approach : " + knapsackmemoized(wt, profit, capacity, n));
  System.out.println("Maximum value using Top Down Approach : " + knapsacktopdown(wt, profit, capacity, n));

 }

}

Problem 2 — Subset Sum Problem

GFG Link — https://www.geeksforgeeks.org/subset-sum-problem-dp-25/

Given —

1. arr[] is nothing but set = 2, 3, 7, 8, 10
2. sum = 11
3. Output = if there is a subset of the given set whose sum is equal to the given sum. Then return true otherwise false.

Top Down Approach

Size of set = n = 5;

sum = w = 11;

we will create a 2D array of dimension (n+1) X (w+1)

Base condition

Base condition 1 : suppose sum = 0,(first column)

Can we have subset whose sum is zero? Obviously for empty subset we can have sum = 0;

Hence for all row , first column will be true.

Base condition 2 : n=0 that is there is no item in the set, and we have sum values 1, 2, 3,4,5,6,7,8,9,10,11

is it possible to get sum=(any value 1,2,..11) from no element. Not possible, we should have at least one item.

Hence, for first row, except first column other column will be false.

Let’s see code implementation in java

package com.dynamicprogramming.knapsack;

public class SubSetSumProble {

 static boolean subSetSumProblem(int[] set, int sum) {

  if (sum < 0) {
   return false;
  }

  int n = set.length;

  // create 2d array of dimension (n+1) * (sum+1)
  boolean[][] t = new boolean[n + 1][sum + 1];

  // fill first row
  for (int i = 0; i < sum + 1; i++) {
   t[0][i] = false;
  }

  // fill first column
  for (int i = 0; i < n + 1; i++) {
   t[i][0] = true;
  }

  for (int i = 1; i < n + 1; i++) {
   for (int j = 1; j < sum + 1; j++) {
    if (set[i - 1] <= j) {
     t[i][j] = t[i - 1][j - set[i - 1]] || t[i - 1][j];
    } else {
     t[i][j] = t[i - 1][j];
    }
   }
  }

  return t[n][sum];

 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub

  int[] set = { 3, 34, 4, 12, 5, 2 };
  int sum = 9;
  System.out.println(subSetSumProblem(set, sum)); // Output: true

  int[] set2 = { 2, 3, 7, 8, 10 };
  System.out.println(subSetSumProblem(set2, 11)); // Output: true

  System.out.println(subSetSumProblem(set2, -1)); // Output: false

  System.out.println(subSetSumProblem(set2, 14)); // Output: false

 }

}