Algorithm | 01 knapsack question DP

01 knapsack question is a very famous dynamic programming question, and it worths looking into the detail. In this article, I will start with the leetcode question 416. Partition Equal Subset Sum, and conclude multiple occasions of this kind of question.

Leetcode 416. Partition Equal Subset Sum

Question

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Solution:

Method 1: 2-D DP question

This question requires us to think the question in a opposite way. If the array can be splited into 2 equal sum subset(for each one of the subsets, the sum is total_sum / 2).
Now this question is changed into a another question: can we find a subset in the array, whose sum is expected sum?
- for each number in the subset, we can assume it is the last number to be added to the subset, we have nums[i] + previous sum = half of the sum.
- the question is then transfered to if we need to pick current value into the subset? So it is a 01 knapsack question.

we create a 2-D boolean matrix called dp: dp[nums.length + 1][expect sum value + 1]. First index means we have up to i values from array, second index means the expected value and value means: is it position to get j with previous i numbers from the array?

initialization:
- dp[0][0] = true // we want 0 and we have nothing, possible.
- dp[i][nums[i -1]] = true // we have that value and we want that value.

state transfer funtion

dp[i][j] = dp[i - 1][j]

dp[i - 1][j - nums[i - 1]]

dp[i - 1][j]: we don’t even need current value, previous subset has already create the expected sum.
dp[i - 1][j - nums[i - 1]]: we use current value nums[i - 1] as the last value add to the subset, if prevous sum can be j - nums[i - 1], we can get the expected sum.

return: dp[nums.length][expect]

  class Solution {
 public boolean canPartition(int[] nums) {
  int sum = 0;
  for(int n : nums) sum += n;
  if((sum & 1) != 0) return false;
  int expect = sum >> 1;
  boolean[][] dp = new boolean[nums.length + 1][expect + 1];
  for(int i = 1; i <= nums.length; i++){
      if(nums[i - 1] > expect) return false;
      dp[i][nums[i - 1]] = true;
      dp[i][0] = true;
  }
  dp[0][0] = true;   
  for(int i = 1; i <= nums.length; i++){
      for(int j = 1; j <= expect; j++){
          dp[i][j] = dp[i - 1][j];
          if(nums[i - 1] <= j)
              dp[i][j] = (dp[i][j] || dp[i - 1][j - nums[i - 1]]);
      }
  }
  return dp[nums.length][expect];
 }
  }

Method 2: 1-D dp

we create a 1-D boolean array dp[expect + 1] for keeping the result when we only have previous i numbers in the original array.
we need to traversal all numbers in the array. If dp[i] == true, it means dp[i + n] = true.

Once we find dp[half_sum] == true, we can return true;

  class Solution {
  public boolean canPartition(int[] nums) {
      int sum = 0;
      for(int n : nums) sum += n;
      if((sum & 1) == 1) return false;
      boolean[] dp = new boolean[sum + 1];
      dp[0] = true;
      for(int n : nums){
          for(int i = sum; i >= 0; i--){
              if(dp[i]) dp[i + n] = true;
          }
          if(dp[sum >> 1]) return true;
      }
      return false;
  }
  }

Classic 01Knapsack question

Question:

We want to get max value with given weight., W = 4

-	0	1	2	3
w	1	1	2	2
v	1	2	4	5

transfer table

-	1	2	3	4
0	-	-	-	-
1	1	-	-	-
2	2	3	-	-
3	2	4	6	7
4	2	5	7	9

Solution:

Method 1: 2-D dp
1. We need to create a 2-D array dp[i][j], i means we take the previous i items and j is the maximum weight at current stage and the value stored in the matrix represents the max value.
2. For each station dp[i][j]:
  - current item doesn’t have to be stored in the bag
    - dp[i][j] = dp[i - 1][j]
  - current value can be stored in the bag
    - dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
    - Here means we are comparing not put the item into the bag and put the item into the bag condition.
```
 public static int maxValue(int[] value, int[] weight, int w){
  int len = value.length;
  int[][] dp = new int[len + 1][w + 1];
  int max = 0;
  for(int i = 1; i <= len; i++){
  for(int j = 1; j <= w; j++){
      if(weight[i - 1] > j){
          dp[i][j] = dp[i - 1][j];
      }else{
          dp[i][j] = Math.max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i - 1][j]);
      }
      max = Math.max(max, dp[i][j]);
  }
  }
  return max;
 }
```

Method 2: We only use a 1-D array to store the maximum value.

  public static int maxValue1(int[] value, int[] weight, int w){
      int len = value.length;
      int[] dp = new int[w + 1];
      int max = 0;
      for(int i = 1; i <= len; i++){
          for(int j = w; j >= 1; j--){
              if(weight[i - 1] <= j){
                  dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
              }
          }
      }
      return dp[w];
  }

Reference

花花酱 Knapsack Problem 背包问题 2 - 刷题找工作 SP11