Knapsack Problem

Problem Domain

Given n items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.

• Two-dimensional DP

• memo[w][i]: for items in item[i...], if the volume of the backpack is w, the maximum value it can hold is memo[w][i].

• Types

  • 0-1 knapsack: an item can only be picked once
    • Q474, Q494, Q1235
  • Bounded knapsack: there are certain number of copies of each item
  • Unbounded knapsack: no upper bound on the number of copies of each kind of item
    • Q322, Q518

---

Perfect Squares

• class Solution {
      public int numSquares(int n) {
          Integer[][] memo = new Integer[n + 1][101];
          return dp(n, 100, memo);
      }
  
      private int dp(int n, int i, Integer[][] memo) {
          if (n == 0)
              return 0;
          if (i == 0)
              return Integer.MAX_VALUE;
          if (memo[n][i] != null)
              return memo[n][i];
  
          int square = i * i, res = dp(n, i - 1, memo);
          if (n >= square)
              res = Math.min(res, 1 + dp(n - square, i, memo));
          return memo[n][i] = res;
      }
  }

Coin Change

// Bottom-up
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin < 0 || dp[i - coin] == -1)
                    continue;
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
            if (dp[i] == amount + 1)
                dp[i] = -1;
        }

        return dp[amount];
    }
}

// Top-down

// counterexample: [1, 5, 7], amount = 11

class Solution {
    public int coinChange(int[] coins, int amount) {
        // unbounded knapsack

        // fewest coins to make up j amount
        Integer[] memo = new Integer[amount + 1];

        return dp(coins, amount, memo);
    }

    private int dp(int[] coins, int amount, Integer[] memo) {
        if (amount == 0) {
            return 0;
        }
        if (memo[amount] != null) {
            return memo[amount];
        }

        int result = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (amount >= coin) {
                int tmp = dp(coins, amount - coin, memo);
                if (tmp != -1) {
                    result = Math.min(tmp, result);
                }
            }
        }
        result = (result == Integer.MAX_VALUE ? -1 : result + 1);
        memo[amount] = result;

        return result;
    }
}

Combination Sum IV

• Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

class Solution {
    public int combinationSum4(int[] nums, int target) {
        Integer[] memo = new Integer[target + 1];
        return dp(target, nums, memo);
    }

    private int dp(int target,int nums[], Integer[] memo) {
        if (target == 0)
            return 1;
        if (memo[target] != null)
            return memo[target];

        int res = 0;
        for (int num : nums) {
            if (target < num)
                continue;
            res += dp(target - num, nums, memo);
        }

        return memo[target] = res;
    }
}

Partition Equal Subset Sum

• class Solution {
      public boolean canPartition(int[] nums) {
          int sum = sum(nums);
  
          if (sum % 2 != 0)
              return false;
  
          int target = sum / 2;
          Boolean[][] memo = new Boolean[target + 1][nums.length];
  
          return dp(nums, 0, target, memo);
      }
  
      private boolean dp(int[] nums, int i, int target, Boolean[][] memo) {
          if (target == 0)
              return true;
  
          if (target < 0 || i == nums.length)
              return false;
  
          if (memo[target][i] != null)
              return memo[target][i];
  
          memo[target][i] = dp(nums, i + 1, target - nums[i], memo) || dp(nums, i + 1, target, memo);
  
          return memo[target][i];
      }
  
      private int sum(int[] nums) {
          int sum = 0;
          for (int num : nums)    sum += num;
          return sum;
      }
  }

Ones and Zeroes

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 0-1 knapsack

        // maximum amount of strings can be put into the knapsack with constraints m, n, within the range [i...)
        Integer[][][] memo = new Integer[strs.length + 1][m + 1][n + 1];

        int[] zeros = new int[strs.length];
        int[] ones = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            int one = 0, zero = 0;
            for (int c = 0; c < s.length(); c++) {
                if (s.charAt(c) == '1') {
                    one++;
                }
                else {
                    zero++;
                }
            }
            zeros[i] = zero;
            ones[i] = one;
        }

        return dp(strs, m, n, 0, memo, zeros, ones);
    }

    private int dp(String[] strs, int m, int n, int available, Integer[][][] memo, int[] zeros, int[] ones) {
        if (available == strs.length) {
            return 0;
        }
        if (m < 0 || n < 0) {
            return 0;
        }
        if (memo[available][m][n] != null) {
            return memo[available][m][n];
        }

        int result = 0;
        int zero = zeros[available], one = ones[available];
        if (zero <= m && one <= n) {
            result = Math.max(
                    dp(strs, m - zero, n - one, available + 1, memo, zeros, ones) + 1,
                    dp(strs, m, n, available + 1, memo, zeros, ones)
            );
        }
        else {
            result = dp(strs, m, n, available + 1, memo, zeros, ones);
        }
        memo[available][m][n] = result;

        return result;
    }
}

Target Sum

class Solution {
    static final int MAX_SUM = 2000;
    public int findTargetSumWays(int[] nums, int target) {
        // 0-1 knapsack

        // sum [0, 1000]    target [-1000, 1000]
        Integer[][] memo = new Integer[nums.length + 1][MAX_SUM * 2 + 1];

        return dp(nums, target, 0, memo);
    }

    private int dp(int[] nums, int target, int available, Integer[][] memo) {
        int index = target + MAX_SUM;

        if (available == nums.length) {
            return target == 0 ? 1 : 0;
        }
        if (memo[available][index] != null) {
            return memo[available][index];
        }

        int result = dp(nums, target - nums[available], available + 1, memo) +
                dp(nums, target + nums[available], available + 1, memo);
        memo[available][index] = result;

        return result;
    }
}

• Another idea:

  首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：

  sum(A) - sum(B) = target
  sum(A) = target + sum(B)
  sum(A) + sum(A) = target + sum(B) + sum(A)
  2 * sum(A) = target + sum(nums)

  综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？

Coin Change II

• Solution

class Solution {
    public int change(int amount, int[] coins) {
        // unbounded knapsack

        // number of combinations to make up i amount with coins ranging from [j...)
        Integer[][] memo = new Integer[amount + 1][coins.length + 1];

        return dp(coins, amount, 0, memo);
    }

    private int dp(int[] coins, int amount, int available, Integer[][] memo) {
        if (amount == 0) {
            return 1;
        }
        if (available == coins.length) {
            return 0;
        }
        if (memo[amount][available] != null) {
            return memo[amount][available];
        }

        int result = 0;
        int coin = coins[available];
        if (amount >= coin) {
            result += dp(coins, amount - coin, available, memo) +
                    dp(coins, amount, available + 1, memo);
        }
        else {
            result += dp(coins, amount, available + 1, memo);
        }
        memo[amount][available] = result;

        return result;
    }
}

Maximum Profit in Job Scheduling

class Solution {

    record Job(
            int startTime,
            int endTime,
            int profit
    ) {}


    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // 0-1 knapsack
        List<Job> jobs = getJobs(startTime, endTime, profit);
        Integer[] memo = new Integer[startTime.length + 1];

        return dp(jobs, 0, memo);
    }

    private int dp(List<Job> jobs, int available, Integer[] memo) {
        if (available == jobs.size()) {
            return 0;
        }
        if (memo[available] != null) {
            return memo[available];
        }

        // not take current job
        int result = dp(jobs, available + 1, memo);
        // take current job
        Job curr = jobs.get(available);
        // binary search next available job
        int next = binarySearch(jobs, available + 1, curr.endTime);
        result = Math.max(dp(jobs, next, memo) + curr.profit, result);
        memo[available] = result;

        return result;
    }

    // [left, right]
    // find first element which value is greater than or equal to key
    // if no, return list size
    private int binarySearch(List<Job> jobs, int leftBound, int key) {
        if (leftBound == jobs.size() || jobs.getLast().startTime < key) {
            return jobs.size();
        }

        int left = leftBound, right = jobs.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (jobs.get(mid).startTime < key) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }

        return left;
    }

    private List<Job> getJobs(int[] startTime, int[] endTime, int[] profit) {
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < startTime.length; i++) {
            jobs.add(new Job(startTime[i], endTime[i], profit[i]));
        }
        Collections.sort(jobs, (a, b) -> a.startTime != b.startTime ?
                Integer.compare(a.startTime, b.startTime) :
                Integer.compare(a.endTime, b.endTime));

        return jobs;
    }
}