背包问题
什么是背包问题
有一个容量为W的背包；现在有一些货品（体积wi，价值vi），总数为n。如果将一个货品放入背包，会消耗掉背包wi的空间，但同时会收获vi的价值。现在需要一个方案，选择一些物品，使背包能够装下，同时，收获的价值最大。这个问题就是背包问题~
0-1背包问题
0-1背包问题是指针对一个货品，不能拆分，即如果选择装入背包，就要一整个装入，会占题集wi，收获价值vi；不能只装一部分；同时每个物品被选择的话，不能选择一次！
那么针对0-1背包，其实可以找所有物品的组合，在能够满足货品和＜W的组合里面，价值最大的一个组合即可。 但是如果货品很多，组合就有2^n，搜索空间很大。
这里用动态规划求解，首先分析状态转移方程。用一个二维数组dp表示各个货品i，在背包重量为j的情况下（j<W)，能够装下货品的最大价值，行对应每个货品，列对应可能的背包重量。
如果当前背包容量j < wi，那么背包根本装不下货品i，此时dp[i][j] = dp[i-1][j]。在当前背包容量j > wi的前提下，针对一个货品有两个方案：
- ①不装入：那么不消耗背包体积，也不增加背包货品价值，可得
dp[i][j] = dp[i-1][j]； - ②装入：装入会获得价值vi，但也会占一定的背包体积，剩余背包体积为j- wi，再去找1~i-1（即货品i前面的货品）在背包容量为j-wi的情况下，能够获得的最大价值，
dp[i][j] = dp[i-1][j - wi] + vi。
但是别忘了，我们是要找最大值，那么就是要将装入or不装入两种情况的dp[i][j]对比，选最大；且只有在w>wi的时候，才有两种选择，因此最终：if(j > wi): dp[i][j] = max( dp[i-1][j] , dp[i-1][j - wi] + vi); else: dp[i][j] = dp[i-1][j]。我们遍历dp这个二维数组，更新dp[i][j]即可，最终结果就是的dp[n][W]。
我们可以在空间上进行优化，考虑用一维dp进行状态转移。在j>wi时，货品i可能被选择装入，我们更新dp[i][j]的时候，在列上会选择j-wi的列，即dp[i-1][j-wi]，事实时j - wi < j，是j前面的列。因此当我改用一维dp进行状态转移的时候，需要从j = W开始往前遍历，因为前面的列，我们在状态转移的时候需要用到，它们需要维持没考虑货品i时的状态。最终状态转移：dp[j] = max(dp[j], dp[j - wi])。
分数背包
分数背包和0-1背包不同的点，在于货品可以拆分，假设在货品i前面加一个系数k(范围是[0,1]），那么状态转移如下:
完全背包问题
完全背包和0-1背包不同的点，在于每个货品有无限个，可以选择多个，但是不能多于k = W/wi，那么状态转移方程如下：
重复背包问题
重复背包和完全背包不同的是，重复背包给每个货品限制了最多可以选择n_i，其状态转移方程如下：
背包问题例题
下面两个问题是经典的背包问题！
416. 分割等和子集
416. 分割等和子集——题目内容如下👇
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
理解题目，转换一下👉在数组中找一些元素（一个子集），使其和为所有元素之和（sum）的一半（target）。这就转换成背包问题了。但不同的点在于：背包问题是<=W，然后找价值v的最大值；这里就是找和=target。
还是用一维dp表示状态转移【节省空间，二维也是可以的】，这个dp是一个boolean的一维数组，dp[i]表示是否有子集和为i。针对nums中的每一个元素num，有两种情况：①选择，那么就要去判断num之前的元素，能不能选出几个使其和为i-num？ 即dp[i] = dp[ i - num]；②不选择，dp[i] = dp[i]；这两种情况只要有一个为true，即可认为nums中有子集和可以为i。因此dp[i] = dp[i] || dp[i-num]。
这里有一些可以提前判断的情况：
- 所有元素和sum为奇数，那么必不可能有子集为其一半，因为分不出一半；
- nums只有一个元素的时候，且元素不能为0，无法拆分成两个子集了。
- nums中有一个最大元素maxNum，该元素大于sum的一半，
sum - maxNum < maxNum，即除去maxNum剩余元素之不可能等于maxNum，maxNum也不能拆分，直接返回false。
dp初始化全为false，dp[0] = true用于判断边界：某一元素num = i时，dp[i-num] = dp[0] =true。 Java版本代码如下：
class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
if(len < 2)
return false;
int sum = 0, maxNum = 0;
for(int i = 0; i < len; i++){
sum += nums[i];
maxNum = Math.max(maxNum, nums[i]);
}
if(sum % 2 == 1 || sum - maxNum < maxNum)
return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for(int i = 0; i < len; i++){
for(int j = target ; j >= nums[i]; j--){
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
}
474. 一和零
474. 一和零 ——题目内容如下👇
给你一个二进制字符串数组
strs和两个整数m和n。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
根据题意，会发现这就是背包问题！背包的容量W，在这里就是m个0和n个1。相当于原来的背包只有容量W一个限制，现在有两个限制。背包问题用一个二维数组记录各个状态，那么这里需要三维数组。同样的，可以进行空间优化，因此用二维数组dp表示状态转移，dp[i][j]表示能够满足包括少于等于i个0，少于等于j个1的最大子集长度。对于strs中的每一个字符串str，有两种可能：①选择，那么对应的长度为dp[i][j] = dp[i-zeros][j-ones] + 1；②不选择，那么dp[i][j] = dp[i][j]。当然，选择str的前提是，i >= zeros，j >= ones。因此得到最终的状态转移过程：
- dp[i][j] = max( dp[i][j] ，dp[i-zeros][j-ones]), if i >= zeros，j >= ones
- dp[i][j] = dp[i][j], otherwise
注意，用二维数组进行状态转移时，针对strs中每个str会更新一轮数组，更新规则是从右下角开始的，从后往前，从下往上。理由是i-zeors < i，j-ones < j，之前的行和列需要保持上一轮状态。Java代码如下：
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] subNum = new int[m+1][n+1];
int len = strs.length;
for(int i = 0; i < len; i++){
int ones = getOnes(strs[i]);
int zeros = strs[i].length() - ones;
for(int j = m; j >= zeros; j--)
for(int k = n; k >= ones; k--)
subNum[j][k] = Math.max(subNum[j][k], subNum[j - zeros][k -ones] +1);
}
return subNum[m][n];
}
public int getOnes(String str){
int ones =0;
int len = str.length();
for(int i = 0; i < len; i++)
ones += (str.charAt(i) - 48);
return ones;
}
}
完全平方数
下面的两个题目其实就是一维的动态规划，不是严格的背包问题。但是两个题目后下面排列组合的问题有关联。 且两个题目非常的相似，因从也整理在这里了。
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
既然是动态规划，我们用一个一维数组dp来表示转换过程。dp[i]即表示和为i的完全平方数的最少数量。对于整数i，待选的完全平方数j的范围是1~sqrt(i)，那么就遍历每一个j，然后找到dp[i - j*j]里面的最小者，然后再+1，就是dp[i]了：dp[i] = 1 + min(dp[i - j\*j] ， 1<=j <=sqrt(i)。相当于假设遍历可能参与相加使得和为i的完全平方数j，这个j参与相加，还需要找一些完全平方数使其和为i- j*j，dp[i - j*j]已经找到了；目的是找最少数量，因此要找最小的dp[i-j*j]。
java代码如下：
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
dp[0]=0;
for(int i = 1; i <= n; i++){
int minFront = Integer.MAX_VALUE;
for(int j = 1; j*j <= i;j++)
minFront = Math.min(minFront, dp[i - j*j]);
dp[i] = 1 + minFront;
}
return dp[n];
}
}
322. 零钱兑换
给你一个整数数组
coins，表示不同面额的硬币；以及一个整数amount，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
其实这个题目和上面的完全平方数非常的类似，完全平方数中供选择的是完全平方数j，且j*j <i；这个题目可供选择的是coins中的硬币coin，且coin < i。同样用一维dp表示状态转移，dp[i]表示用coins中最少数量的硬币，组成i元。遍历coins中的小于i的硬币coin：dp[i] = min( dp[i - coin]) + 1。
完全平方数中，不论怎么样，都可以由无数的1组成，但是这个coins中的硬币可能没有1，那么有些i可能就没有硬币组合方案，结果为-1。考虑初始化dp的时候将其设置成amount + 1，因为就算是全部由1组成也只需要amount个1，这样如果dp[i] = amount + 1 就表示没有方案。
java代码如下：
class Solution {
public int coinChange(int[] coins, int amount) {
int[] minCur = new int [amount+1];
int max = amount + 1;
Arrays.fill(minCur, max);
// 先将coins排序，后续不用对所有i都遍历一整个coins数组了
Arrays.sort(coins);
minCur[0] = 0;
int n = coins.length;
for(int i = 1; i <= amount; i++)
for(int j = 0; j < n && coins[j] <= i; j++ ){
minCur[i] = Math.min(minCur[i], minCur[i-coins[j]] + 1);
}
return minCur[amount] > amount ? -1: minCur[amount];
}
}
排列与组合
排列和组合的区别，排列考虑位置，组合不考虑位置。排列中(1,2)与(2,1)是不一样的，但是组合中这两个就是重复的。
组合，无重复：518. 零钱兑换 II
给你一个整数数组
coins表示不同面额的硬币，另给一个整数amount表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
这个题目是返回硬币的组合数，即组合方案数量。一开始我的想法是：对于coins中的coin，更新的dp[i]，dp[i] = sum( dp[i - coin] )，但这是有问题的。比如coins = [1,2]，amount = 3，dp[0] = 1, dp[1] = dp[1-1] = 1, dp[2] = dp[2-1] + dp[2-2] =2, dp[3] = dp[3-1] + dp[3-2] = 3。
结果是错误的，因此dp[3-1]考虑了1 + 2和 1 +1 +1，但是dp[3-2]又考虑了2 + 1，里面就有重复。
正确的避免这种重复的办法是，固定住待选择的零钱集合，假设一开始参与组合的只有coin[0]，然后是{coin[0],coin[1]}，然后是{coin[0],coin[1],coin[2]}依次增加一个硬币coin[i]，这样做就避免了i < j时，x = coin[i] + coin[j] 与coin = coin[j] + coin[i]这种情况，因为候选硬币为coin[0~i]的时候，coin[j]没有参与！
整理一下，就是依次遍历coins中的硬币coin，考虑加入coin这个候选硬币后，新增的组合数：dp[i] += dp[i - coin]
java代码如下：
class Solution {
public int change(int amount, int[] coins) {
int[] num = new int[amount + 1];
int n = coins.length;
num[0] = 1;
//排序不排序都一样的
Arrays.sort(coins);
//一次新增coin[i]这个候选硬币
for(int i = 0; i < n; i++){
for(int j = coins[i];j <= amount; j++)
num[j] += num[j - coins[i]];
}
return num[amount];
}
}
排列，可重复：377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
只看题目文字，会发现和零钱兑换不是一模一样吗！但是一看例子，原来这个是数字顺序不一样就行，那就是排列问题！那么遍历coins中的每个coin，dp[i] = sum(dp[i - coin])，其实遍历coins中的coin，选中一个coin的时候，就相当于固定了这个coin的位置，那么就是一种排列，比如 3 = 1 + 2，3 = 2 + 1，前面一种先固定了coin = 1，第二种是先固定了coin = 2。
java代码如下：
class Solution {
public int combinationSum4(int[] nums, int target) {
int n = nums.length;
int[] count = new int[target+1];
count[0] = 1;
Arrays.sort(nums);
for(int i = 1; i <= target; i++){
for(int j = 0; j < n && nums[j] <= i; j++)
count[i] += count[i - nums[j]];
}
return count[target];
}
}
