背包问题设定和相关变体
1 个背包有个最大容量, 多个物品, 每个物品有 [重量] 和 [价值] 两个属性, 多个物品的放入背包有以下几种设定
(i). 每个物品只有 1 个, 对每个种类的物品只有 [选一个] 或者 [不选] => 0-1 背包
(ii). 每个物品都可以重复选无数个, 也就是每个物品都可以 [选任意几个] 或者 [不选] => 完全背包
(iii). 每个的物品数量有上限, 也就是每个物品都可以 [选至多几个] 或者 [不选] => 多重背包
(iv). 按某种组打包, 每组最多选一个 => 分组背包
0-1背包
朴素0-1背包
给一个可装载重量为 W 的背包和 N 个物品, 每个物品有重量和价值两个属性, 其中第 i 个 (i从1开始计数) 物品的重量为 w[i] 且价值为 v[i], 对应给定的索引是 w[i-1] 和 v[i-1], 现在用这个背包装物品, 最多能装的价值是多少?
示例1: N=3, W=4, w=[2,1,3], v=[4,2,3] 输出: 6 (选择前两个进入背包)
分析:
1.状态这里有两个, 第一个状态是已选择的物品集合或者说有哪些物品被放入, 就是多个物品的组合; 另一个状态是当前背包的容量, 有多个容量可变的背包, 我们只需要找这些背包里面满足要求的这些背包
2.结合上述状态的定义, 最简单的方法是把定义好的两种状态编码在二维数组里, 我们定义 dp[i][j] 为对于前 i 个物品, 当前的背包容量为 j 的情况下, 这种情况可以装下的最大价值为 dp[i][j]
3.我们这里的选择是什么? 针对每一个物品, 我们的选择是
(i). 放入背包
(ii). 不放入背包
所以当前的状态的价值 dp[i][j] = max(i放入背包的价值, i不放入背包的价值)
(i). i 不放入背包的价值为前 i-1 个物品选择完后最大价值 dp[i][j] = dp[i-1][j]
(ii). i 放入背包的价值为 dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1], 这里代表的意义是如果装了第 i 个商品, 那么需要找剩余重量 j-w[i-1] 限制下的最大价值, 然后加上第 i 个商品的的价值 v[i-1]
遍历所有的单个物品的状态以及背包容量的状态, 然后依次决策当前物品是否可以被放入
void knapsack(W, N, w, v) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= W; ++j) {
// dp[i][j] = max(把物品i装入, 不把物品i装入)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
}
}
return dp[N][M]:
}
4.每次尝试放入的时候, 都需要对 i 放入的时候得判断还有足够的容量放入背包
// 如果不能放入背包, 状态取前一个状态
if (w[i-1] > j) {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
}
5.判断下 base 条件, dp[0][i] = ? 和 dp[i][0] = ? 想一下含义, 没有任何东西装备包, 重量不管是多少, 价值都是 0; 总重量为 0, 不管要装多少个东西, 总价值 = 0; dp[0][j] = 0; dp[i][0] = 0; 综合上述分析, 给出 0-1 背包的基本形式
class Solution {
public:
int knapsack(int W, int N, vector<int>&w, vector<int>& v) {
vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= W; ++j) {
if (j < w[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
}
}
}
return dp[N][W];
}
};
6.我们仔细分析下这个状态转移
dp[i][j] = max(dp[i-1][j], dp[i-1][w-coin[i]] + v[i-1])
发现第 1 个维度都是 i-1, 也就是 2 种转移模式下的物品状态转移结果都是由前一个物品状态转移过来, 尝试压缩到 1 个维度用 1 维数组
定义一维状态 dp[j] 为 容量为 j 的背包的最大价值; 那么状态转移 dp[j] 是怎么来的, 容量为 j 的背包的价值 dp[j] = dp[j - w[i]] + v[i] 也就是通过放入物品 i 转移过来, 我们只迭代 dp[j] 的价值
因此状态转移为
dp[j] = max(dp[j], dp[j - w[i]] + v[i-1])
因此完整的 dp 过程为
// 遍历物品
for (int i = 0; i < N; ++i) {
// 遍历背包容量: 倒序遍历保证容量
for (int j = W; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
7.为什么遍历背包容量的时候, 要倒序遍历背包容量?
dp[j] = dp[j] || dp[j - nums[i]]
可以理解为 dp[j] (新) = dp[j] (旧) || dp[j - nums[i]] (旧), 如果采用正序的话 dp[j - nums[i]] 会被之前的操作覆盖掉
416.分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
分析:
1.子集划分的存在性, 本质上是组合的存在性; 组合的存在性, 其实是满足某个约束条件下的背包问题; 我们回顾背包问题, 背包问题是给定的物品和重量下找最大的价值的一种组合, 这个问题是找一种划分，其实也就是找一种组合正好满足组合之和等于 sum/2: 也就是给定一个重量为 sum/2 的背包, 以及 N 个物品, 每个物品的重量为 nums[i], 问是否存在一种装背包的装法, 使得恰好把背包装满了
2.还原出来背包问题的本质, 那么我们就可也用 0-1 背包来解问题了, 我们对状态的存在性进行状态描述, 因此用一个 bool 类型的变量
(i). dp[i][j] = true 表示用前 i 个元素进行组合, 存在一个组合使得前 i 个元素之和恰好为 j, 注意用前 i 个元素组合隐含一种可能性是什么都不用的情况;
(ii) dp[i][j] = false 表示用前 i 个元素进行选择组合, 不存在一个组合使得前 i 个元素之和恰好为 j;
我们想要最终的结果就是 dp[i][sum/2] 的结果
3.base case 这里需要想一下, dp[i][0] = ? dp[0][i] = ?
(i). 对于前一种情况, 相当于用前 i 个元素进行组合, 存在一个组合使得前 i 个元素之和恰好为 0, 因为可以不选择任何元素, 所以都是这种可能性都存在的, 因此 dp[i][0] = true
(ii). 对于后一种情况, 相当于用前 0 个元素进行组合, 存在一个组合使得前 0 个元素之和恰好为 i, 这可能性都不存在, 因此 dp[0][i] = false
4.除了上述的条件, 我们对一些特殊情况进行特殊处理, 先判断掉不可能的结果, 再去做背包状态转移
(i). 元素个数为1, 不存在划分
(ii). 所有元素总和为奇数, 不存在划分
class Solution {
public:
bool canPartition(vector<int>& nums) {
int len = nums.size();
// 长度 <= 1 不可分割
if (len <= 1) {
return false;
}
int sum = 0;
// 元素总和为奇数 不可分割
for (auto& x: nums) {
sum += x;
}
if (sum % 2 == 1) {
return false;
}
sum /= 2;
vector<vector<bool>> dp(len+1, vector<bool>(sum+1, false));
// base条件: 用前 i 个元素进行组合, 存在一个组合使得前 i 个元素之和恰好为 0
for (int i = 0; i <= len; ++i) {
dp[i][0] = true;
}
for (int i = 1; i <= len; ++i) {
for (int j = 1; j <= sum+1; ++j) {
if (nums[i-1] > j) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}
return dp[len][sum];
}
};
将二维的背包转化成一维的背包, 在背包问题中是 dp[j] 表示容量为 j 的时候的最大价值, 在本题里面表示求和为 j 的时候的是否存在组合, 核心的状态转移为
dp[j] = dp[j] || dp[j-nums[i-1]]
class Solution {
public:
bool canPartition(vector<int>& nums) {
int len = nums.size();
// 长度 <= 1 不可分割
if (len <= 1) {
return false;
}
int sum = 0;
// 元素总和为奇数 不可分割
for (auto& x: nums) {
sum += x;
}
if (sum % 2 == 1) {
return false;
}
sum /= 2;
vector<bool> dp(sum+1, false);
dp[0] = true;
// 遍历元素
for (int i = 0; i < len; ++i) {
// 倒序遍历和
for (int j = sum; j >= i; --j) {
if (nums[i] <= j) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
};
1049.最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：输入：stones = [2,7,4,1,8,1] 输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：输入：stones = [31,26,33,21,40] 输出：5
分析:
1.1046 从最大的两块石头去碰撞, 这里需要任意选择两块去碰撞, 然后达到剩下的重量最小的效果; 首先需要分析怎么才能达到剩下的石头最小重量的效果
2.经过分析发现, 我们可以将整体石头分成两堆, 重量分别为 heap1 和 heap2, 不妨设 heap1 >= heap2, 这样最终的结果就是 heap1-heap2, 我们需要保证 heap1-heap2 是最小的
3.heap1-heap2结果最小, 两个同时划分不好分析, 想办法转化成算一个heap的结果,也就是算heap1或者heap2, 我们注意到另一组关系是 sum=heap1+heap2, 这个sum是已知的
4.进而 heap1-heap2 = sum - 2 heap2, 我们希望求 heap1-heap2 的最小值, 那么就是转化成求sum-2 heap2的最小值, 进一步推导等价于求heap2 <= sum/2 的最大值
5.这样就转化成了一个 0-1 背包的问题, 任意选 i 块石头, 使他们的总重量趋近于总重量的一半, 背包最大容量是 sum/2, 石头的重量和价值都是 stone[i]
6.重新定义问题 dp[i][j] 表示选择前i个石头重量是否能凑出重量 j
7.base case分析: dp[i][0] 表示已经装包完成了, 设置成true; dp[0][j]表示没有物品进入, 需要设置成false;
8.所以得到所有的 dp[n][1..m], 需要找到最大的j, 然后算对应的 heap1 = sum-2*heap2
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(), stones.end(), 0);
int n = stones.size();
int m = sum / 2;
vector<vector<int>> dp(n+1, vector<int>(m+1, false));
for (int i = 0; i <= n; ++i) {
dp[i][0] = true;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j < stones[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i-1]];
}
}
}
for (int j = m;;--j) {
if (dp[n][j]) {
return sum - 2*j;
}
}
}
};
494.目标和
给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例 1：输入：nums = [1,1,1,1,1], target = 3 输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3示例 2：输入：nums = [1], target = 1 输出：1
分析:
1.这道题用回溯做非常的简单, 用dp做需要想下
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
}
};
完全背包
518.零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
示例 1：输入：amount = 5, coins = [1, 2, 5] 输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1示例 2：输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：输入：amount = 10, coins = [10] 输出：1
分析:
1.可以看成背包容量为 amount, 有一系列重量为 coins 的物品, 第 i 个物品重量为 coins[i], 每个物品的数量是无限多的, 问下有多少种方法可以恰好把背包装满, 属于完全背包问题
2.和 0-1 背包类似, 我们先用二维 dp 数组来思考这个问题, dp[i][j] 定义为前 i 个物品, 重量为 j 的时候得到的装包的方法个数
3.dp[i][j] 对于第 i 个物品而言, 都有放入和不放入两种状态
(i). 当 i 不放入时候, 重量为 j 的当前的装包数等于选前 i-1 个物品重量为 j 的装包数, 因此一种可能的状态转移为: dp[i][j] = dp[i-1][j]
(ii). 当 i 选择放入的时候, 那么选择 coins[i] 这个硬币装入, 那么就等于凑出来 [j-coins[i-1]] 的装包数, 因此一种可能的状态转移为: dp[i][j] = dp[i][j-coins[i-1]]
4.我们的目标 dp[i][j] 是要求总共有多少中装包方法, 因此装包数就等于以上两种: [i 放入的装包数] 或者 [i 不放入的装包数] 之和
因此状态转移为, dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
5.base case里面 dp[i][0] = 1, 重量为 0 所以不管放前 i 个装包数量均为1, dp[0][j] = 0, 不放入任何的物品所以装包方法为0
class Solution {
public:
int change(int amount, vector<int>& coins) {
if (amount == 0)
return 1;
int n = coins.size();
if (n == 0)
return 0;
vector<vector<int>> dp(n+1, vector<int>(amount+1, 0));
for (int i = 0; i <= n; ++i) {
dp[i][0] = 1;
}
// 遍历物品
for (int i = 1; i <= n; ++i) {
// 遍历金额
for (int j = 1; j <= amount; ++j) {
// 不能放入
if (coins[i-1] > j) {
dp[i][j] = dp[i-1][j];
// 可以放入: 组合数 = 不放入组合数 + 放入组合数
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
}
}
}
return dp[n][amount];
}
};
322.零钱兑换
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
示例 1：输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2：输入：coins = [2], amount = 3 输出：-1
示例 3：输入：coins = [1], amount = 0 输出：0
分析:
1.凑整总金额问题下的最少硬币个数存在重叠子结构, 因此考虑动态规划; 硬币的数量是无限的, 因此可以理解为是完全背包问题, 我们用 dp[i] 表示凑成金额 i 下的最小硬币个数
2.金额为 i 的情况下的最小硬币个数是怎么来的 ? dp[i] 的状态转移为 dp[i - coins[j]] + 1 转移过来
3.base case : dp[0] 表示 凑成金额 i 最小总硬币个数 = 0, 因此 dp[0] = 0
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) {
return 0;
}
int len = coins.size();
if (len == 0) {
return 0;
}
vector<int> dp(amount+1, amount+1);
dp[0] = 0;
// 遍历硬币
for (int i = 0; i < len; ++i) {
// 遍历金额
for (int j = coins[i]; j <= amount; ++j) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == amount+1 ? -1 : dp[amount];
}
};
也可以外层遍历金额, 内层遍历硬币
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) {
return 0;
}
int n = coins.size();
if (n == 0) {
return 0;
}
vector<int> dp(amount+1, amount+1);
dp[0] = 0;
// 遍历金额
for (int i = 1; i <= amount; ++i) {
// 遍历硬币
for (int j = 0; j < n; ++j) {
// 如果当前硬币满足金额要求
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i-coins[j]] + 1);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
};
279.完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：输入：n = 13 输出：2 解释：13 = 4 + 9
分析:
1.[和为x的最少数量] 和 [和为y的最少数量] 是重叠字节结构的关系, 假设和为 i 的最小数量为 dp[i]
2.想想 dp[i] (和为x的最少数量) 是怎么来的呢?
(i). 它可以由前面一个和转过来
(ii). 它可以由前面某一个和为 y 的最少数量 + 1 得来, 其中 [和的差距] 正好是某一个数的平方, 所以我们遍历所有和的空间下, 在遍历所有算数平方根的空间
3.状态转移为 dp[i] = min(dp[i-1], dp[i - j ^ 2]) + 1 , 其中 j*j 的上限为当前求和数
4.边界条件 dp[0] 是和为 0 的完全平方数的最少数量 = 0
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
// 遍历和空间
for (int i = 1; i <= n; ++i) {
// 遍历 算数平方根空间
for (int j = 1; j*j <= i; ++j) {
dp[i] = min(dp[i], dp[i - j*j] + 1);
}
}
return dp[n];
}
};
377.组合总和 Ⅳ：
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。示例 1：输入：nums = [1,2,3], target = 4 输出：7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：输入：nums = [9], target = 3 输出：0
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
}
};
多维背包
1.01 字符构成最多的字符串：多维费用的 0-1 背包最大值，两个背包大小：0和1的数量
2.盈利计划：多维费用的 0-1 背包最大值
分组背包
1.掷骰子的N种方法：每一组是一个骰子，每个骰子只能拿一个体积为1到6的物品
887.鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：
输入：k = 1, n = 2 输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2：输入：k = 2, n = 6 输出：3
示例 3：输入：k = 3, n = 14 输出：4
class Solution {
public:
int superEggDrop(int k, int n) {
}
};
646.最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
}
};
转载请注明来源, from goldandrabbit.github.io
