有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值 。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

  • 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
  • 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。

  1. // W 为背包总体积
  2. // N 为物品数量
  3. // weights 数组存储 N 个物品的重量
  4. // values 数组存储 N 个物品的价值
  5. public int knapsack(int W, int N, int[] weights, int[] values) {
  6.     int[][] dp = new int[N + 1][W + 1];
  7.     for (int i = 1; i <= N; i++) {
  8.         int w = weights[i - 1], v = values[i - 1];
  9.         for (int j = 1; j <= W; j++) {
  10.             if (j >= w) {
  11.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
  12.             } else {
  13.                 dp[i][j] = dp[i - 1][j];
  14.             }
  15.         }
  16.     }
  17.     return dp[N][W];
  18. }

空间优化
在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。
因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。

  1. public int knapsack(int W, int N, int[] weights, int[] values) {
  2.     int[] dp = new int[W + 1];
  3.     for (int i = 1; i <= N; i++) {
  4.         int w = weights[i - 1], v = values[i - 1];
  5.         for (int j = W; j >= 1; j--) {
  6.             if (j >= w) {
  7.                 dp[j] = Math.max(dp[j], dp[j - w] + v);
  8.             }
  9.         }
  10.     }
  11.     return dp[W];
  12. }

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.
变种

  • 完全背包：物品数量为无限个
  • 多重背包：物品数量有限制
  • 多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
  • 其它：物品之间相互约束或者依赖

区别

  • 0-1背包：有N件物品和一个容量为V的背包，第i件物品消耗的容量为Ci，价值为Wi，求解放入哪些物品可以使得背包中总价值最大。两层for循环，外层为第i个物体，内层为容量。
  • 完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用，第i件物品消耗的容量为Ci，价值为Wi，求解放入哪些物品可以使得背包中总价值最大。两层for循环，外层为容量，内层为第i个物体。或转化为0-1背包，三层for循环。
  • 多重背包：有N种物品和一个容量为V的背包，第i种物品最多有Mi件可用，每件物品消耗的容量为Ci，价值为Wi，求解入哪些物品可以使得背包中总价值最大。

状态方程
0-1背包的状态方程：Max{dp[i-1,v], dp[i-1,v-Ci]+w1}
完全背包的状态方程：Max{dp[i-1,v-kCi]+kWi | 0<=kCi<=v}
多重背包的状态方程：Max{dp[i-1,c-kCi]+kWi | 0<=k<=Mi}
三种背包问题都是基于子问题来选取价值最大的一个，只是选择的范围不一样。

416. Partition Equal Subset Sum (Medium)

题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
思路
背包总容量为总和的一半，物体为数组中的每一个数，重量为数的大小，价值为是否等于该重量（true/false）
1.明确dp定义：dp[i][j]表示前i个数是否能组合等于j值。
2.定义base case： dp[0][j]=1, dp[i][0]=0
3.状态转移：dp[i][j] = d[i-1][j] | d[i-1][j-nums[i-1]]

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         if(nums==null || nums.length<2){
  4.             return false;
  5.         }
  6.         int len = nums.length;
  7.         int sum = 0;
  8.         for(int i=0; i<len; i++){
  9.             sum = sum + nums[i];
  10.         }
  11.         if(sum%2!=0){
  12.             return false;
  13.         }
  14.         int weight = sum/2;
  15.         //初始化
  16.         boolean[][] dp = new boolean[len+1][weight+1];
  17.         for(int i=0; i<weight+1; i++){
  18.             dp[0][i] = false;
  19.         }
  20.         for(int i=0; i<len+1; i++){
  21.             dp[i][0] = true;
  22.         }
  23.         //状态转移
  24.         for(int i=1; i<len+1; i++){
  25.             for(int j=1; j<weight+1; j++){
  26.                 dp[i][j] = dp[i-1][j];
  27.                 if(j>=nums[i-1]){
  28.                     dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
  29.                 }
  30.             }
  31.         }
  32.         return dp[len][weight];
  33.     }
  34. }

内存优化

前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。
因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖，倒序来循环求解。

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         if(nums==null || nums.length<2){
  4.             return false;
  5.         }
  6.         int len = nums.length;
  7.         int sum = 0;
  8.         for(int i=0; i<len; i++){
  9.             sum = sum + nums[i];
  10.         }
  11.         if(sum%2!=0){
  12.             return false;
  13.         }
  14.         int weight = sum/2;
  15.         //初始化
  16.         boolean[] dp = new boolean[weight+1];
  17.         dp[0] = true;
  18.         //状态转移
  19.         for(int i=1; i<len+1; i++){
  20.             for(int j=weight; j>0; j--){
  21.                 if(j>=nums[i-1]){
  22.                     dp[j] = dp[j] | dp[j-nums[i-1]];
  23.                 }
  24.             }
  25.         }
  26.         return dp[weight];
  27.     }
  28. }

结果
image.png

494. Target Sum (Medium)

题目描述
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
思路
1.明确dp定义：dp[i][j]表示前i项和等于j的方法数。
2.base case：dp[0][j(-/+)nums[0]]+=1;
3.状态转移：在数组成立的情况下：dp[i][j-minsum] = dp[i-1][p1-minsum]+ dp[i-1][p2-minsum];

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int S) {
  3.         int maxsum = 0;
  4.         int minsum = 0;
  5.         for(int i=0; i<nums.length; i++){
  6.             if(nums[i]>=0){
  7.                 maxsum += nums[i];
  8.                 minsum -= nums[i];
  9.             }else{
  10.                 maxsum -= nums[i];
  11.                 minsum += nums[i];
  12.             }
  13.         }
  14.         if(S<minsum || S>maxsum){
  15.             return 0;
  16.         }
  17.         int len = nums.length;
  18.         int[][] dp = new int[len][maxsum-minsum+1];
  19.         //初始化
  20.         dp[0][nums[0]-minsum]+=1;
  21.         dp[0][-nums[0]-minsum]+=1;
  22.         for(int i=1; i<len; i++){
  23.             for(int j=minsum; j<=maxsum; j++){
  24.                 int p1 = j-nums[i];
  25.                 int p2 = j+nums[i];
  26.                 if(p1>=minsum && p1<=maxsum){
  27.                     dp[i][j-minsum] += dp[i-1][p1-minsum];
  28.                 }
  29.                 if(p2>=minsum && p2<=maxsum){
  30.                     dp[i][j-minsum] += dp[i-1][p2-minsum];
  31.                 }
  32.             }
  33.         }
  34.         return dp[len-1][S-minsum];
  35.     }
  36. }

另一种思路

该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。
可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。
copy 上题的解法：

  1. public int findTargetSumWays(int[] nums, int S) {
  2.     int sum = computeArraySum(nums);
  3.     if (sum < S || (sum + S) % 2 == 1) {
  4.         return 0;
  5.     }
  6.     int W = (sum + S) / 2;
  7.     int[] dp = new int[W + 1];
  8.     dp[0] = 1;
  9.     for (int num : nums) {
  10.         for (int i = W; i >= num; i--) {
  11.             dp[i] = dp[i] + dp[i - num];
  12.         }
  13.     }
  14.     return dp[W];
  15. }
  16. //求和
  17. private int computeArraySum(int[] nums) {
  18.     int sum = 0;
  19.     for (int num : nums) {
  20.         sum += num;
  21.     }
  22.     return sum;
  23. }

结果
image.png

474. Ones and Zeroes (Medium)

题目描述
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

  1. class Solution {
  2.     public int findMaxForm(String[] strs, int m, int n) {
  3.         int len = strs.length;
  4.         List<int[]> list = new ArrayList<>();
  5.         list = countString(strs);
  6.         int[][][] dp = new int[len+1][m+1][n+1];
  7.         for(int x=1; x<len+1; x++){
  8.             int[] tmp = list.get(x-1);
  9.             for(int i=0; i<m+1; i++){
  10.                 for(int j=0; j<n+1; j++){
  11.                     dp[x][i][j] = dp[x-1][i][j];
  12.                     if(tmp[0]<=i && tmp[1]<=j){
  13.                         dp[x][i][j] = Math.max(dp[x][i][j], dp[x-1][i-tmp[0]][j-tmp[1]] + 1);
  14.                     }
  15.                 }
  16.             }
  17.         }
  18.         return dp[len][m][n];
  19.     }
  20.     public List<int[]> countString(String[] strs){
  21.         List<int[]> list = new ArrayList<>();
  22.         int[] tmp;
  23.         for(int i=0; i<strs.length; i++){
  24.             String s = strs[i];
  25.             tmp = new int[2];
  26.             for(int j=0; j<s.length(); j++){
  27.                 char c = s.charAt(j);
  28.                 if(c=='0'){
  29.                     tmp[0]++;
  30.                 }else{
  31.                     tmp[1]++;
  32.                 }
  33.             }
  34.             list.add(tmp);
  35.         }
  36.         return list;
  37.     }
  38. }

内存优化

  1. class Solution {
  2.     public int findMaxForm(String[] strs, int m, int n) {
  3.         int len = strs.length;
  4.         List<int[]> list = new ArrayList<>();
  5.         list = countString(strs);
  6.         int[][] dp = new int[m+1][n+1];
  7.         for(int x=0; x<len; x++){
  8.             int[] tmp = list.get(x);
  9.             for(int i=m; i>=0; i--){
  10.                 for(int j=n; j>=0; j--){
  11.                     if(i>=tmp[0] && j>=tmp[1]){
  12.                         dp[i][j] = Math.max(dp[i][j], dp[i-tmp[0]][j-tmp[1]]+1);
  13.                     }
  14.                 }
  15.             }
  16.         }        
  17.         return dp[m][n];
  18.     }
  19.     public List<int[]> countString(String[] strs){
  20.         List<int[]> list = new ArrayList<>();
  21.         int[] tmp;
  22.         for(int i=0; i<strs.length; i++){
  23.             String s = strs[i];
  24.             tmp = new int[2];
  25.             for(int j=0; j<s.length(); j++){
  26.                 char c = s.charAt(j);
  27.                 if(c=='0'){
  28.                     tmp[0]++;
  29.                 }else{
  30.                     tmp[1]++;
  31.                 }
  32.             }
  33.             list.add(tmp);
  34.         }
  35.         return list;
  36.     }
  37. }

322. Coin Change (Medium)-完全背包

题目描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
思路
注意硬币数量无限。dp[i] = Math.min(min, dp[i-money]+1);

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int len = coins.length;
  4.         int[] dp = new int[amount+1];
  5.         Arrays.fill(dp,-1);
  6.         dp[0] = 0;
  7.         for(int i=1; i<=amount; i++){
  8.             int min = Integer.MAX_VALUE;
  9.             for(int j=0; j<len; j++){
  10.                 int money = coins[j];
  11.                 if(i>=money && dp[i-money]!=-1){
  12.                     min = Math.min(min, dp[i-money]+1);
  13.                 }
  14.             }
  15.             if(min<Integer.MAX_VALUE){
  16.                 dp[i] = min;
  17.             }
  18.         }
  19.         return dp[amount];
  20.     }
  21. }

image.png

完全背包同一格式版

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int[] dp = new int[amount+1];
  4.         Arrays.fill(dp,Integer.MAX_VALUE);
  5.         dp[0] = 0;
  6.         for(int coin:coins){
  7.             for(int i=coin; i<=amount; i++){
  8.                 if(dp[i-coin]!=Integer.MAX_VALUE){
  9.                     dp[i] = Math.min(dp[i], dp[i-coin]+1);
  10.                 }
  11.             }
  12.         }
  13.         if(dp[amount]==Integer.MAX_VALUE) {
  14.             return -1;
  15.         }else {
  16.             return dp[amount];
  17.         }
  18.     }
  19. }

518. Coin Change 2 (Medium)

题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
思路
完全背包，将第二层循环的倒序改为正序。

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         int len = coins.length;
  4.         int[] dp = new int[amount+1];
  5.         dp[0] = 1;
  6.         for(int money:coins){
  7.             for(int i=money; i<=amount; i++){
  8.                 dp[i] += dp[i-money];
  9.             }
  10.         }
  11.         return dp[amount];
  12.     }
  13. }

139. Word Break (Medium)

题目描述
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。
思路
完全背包问题，但是该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中。求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。

  1. class Solution {
  2.     public boolean wordBreak(String s, List<String> wordDict) {
  3.         boolean[] dp = new boolean[s.length()+1];
  4.         dp[0] = true;
  5.         for(int i=0; i<s.length()+1; i++) {
  6.             for(int j=0; j<wordDict.size(); j++) {
  7.                 String ref = wordDict.get(j);
  8.                 int len = ref.length();
  9.                 if(i>=len) {
  10.                     String tmp = s.substring(i-len, i);
  11.                     if(ref.equals(tmp) && dp[i-len]) {
  12.                         dp[i] = true;
  13.                     }
  14.                 }
  15.             }
  16.         }
  17.        return dp[s.length()];
  18.     }
  19. }

结果
image.png

377. Combination Sum IV (Medium)

题目描述
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
思路
同上，涉及顺序的完全背包。

  1. class Solution {
  2.     public int combinationSum4(int[] nums, int target) {
  3.         if(nums==null ||nums.length==0){
  4.             return 0;
  5.         }
  6.         int len = nums.length;
  7.         int[] dp = new int[target+1];
  8.         dp[0] = 1;
  10.         for(int i=1; i<target+1; i++){
  11.             for(int num : nums){
  12.                 if(i>=num && dp[i-num]!=-1){
  13.                     dp[i] += dp[i-num];
  15.                 }
  16.             }
  17.         }
  18.         return dp[target];
  19.     }
  20. }

结果
image.png