【道德经·第二十八章】知其雄，守其雌，为天下溪。为天下溪，常德不离，复归于婴儿。知其白，守其黑，为天下式，为天下式，常德不忒，复归于无极。
本文参考资料来自此处
背包问题的解题模板
二维版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
vector<vector<int> > dp(N+1, vector<int>(W+1, 0));
for(int i = 1; i <= N; i++) {
for(int w = 1; w <= W; w++) {
if(w - wt[i-1] < 0) {
dp[i][w] = dp[i-1][w];
} else {
dp[i][w] = max(dp[i-1][w-wt[i-1]] + val[i-1]),
dp[i-1][w]);
}
}
}
return dp[N][W];
}
|
状态压缩：
1
2
3
4
5
6
7
8
9
10
11
| int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
vector<int> dp(W+1, 0);
for(int i = 1; i <= N; i++) {
for(int j = W; j >= wt[i-1]; j--) {
dp[j] = max(dp[j], dp[j-wt[i-1]]+val[i-1]);
}
}
return dp[W];
}
|
背包问题分类
常见的背包类型主要有以下几种：
- 0/1背包问题：每个元素最多选取一次
- 完全背包问题：每个元素可以重复选择
- 组合背包问题：背包中的物品要考虑顺序
- 分组背包问题：不止一个背包，需要遍历每个背包
而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
- 最值问题：要求最大值/最小值
- 存在问题：是否存在…………，满足…………
- 组合问题：求所有满足……的排列组合
首先是背包分类的模板：
- 0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
- 完全背包：外循环nums,内循环target,target正序且target>=nums[i];
- 组合背包：外循环target,内循环nums,target正序且target>=nums[i];
- 分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板
然后是问题分类的模板：
- 最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
- 存在问题(bool)：dp[i]=dp[i]||dp[i-num];
- 组合问题：dp[i]+=dp[i-num];
从一堆石头中,每次拿两块重量分别为x,y的石头,若x=y,则两块石头均粉碎;若x<y,两块石头变为一块重量为y-x的石头求最后剩下石头的最小重量(若没有剩下返回0)
0/1背包最值问题：外循环stones,内循环target=sum/2倒序,应用转移方程1
1
2
3
4
5
6
7
8
9
| int lastStoneWeightII(vector<int> &stones) {
int sum = accumulate(stones.begin(), stones.end(), 0);
int target = sum / 2;
vector<int> dp(target + 1);
for (int stone : stones)
for (int i = target; i >= stone; i--)
dp[i] = max(dp[i], dp[i - stone] + stone);
return (sum - dp[target]) - dp[target];
}
|
给定amount,求用任意数量不同面值的零钱换到amount所用的最少数量
完全背包最值问题：外循环coins,内循环amount正序,应用状态方程1
1
2
3
4
5
6
7
8
9
10
11
12
13
| int coinChange(vector<int> &coins, int amount) {
vector<long long> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int coin : coins) {
for (int i = 0; i <= amount; i++) {
if (coin <= i)
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount]==INT_MAX ? -1 : dp[amount];
}
|
分割等和子集：判断是否能将一个数组分割为两个子集,其和相等
0-1背包存在性问题：是否存在一个子集,其和为target=sum/2,外循环nums,内循环target倒序,应用状态方程2
1
2
3
4
5
6
7
8
9
10
11
12
| bool canPartition(vector<int> &nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1)
return false;
int target = sum / 2;
vector<int> dp(target + 1, 0);
dp[0] = true;
for (int num : nums)
for (int i = target; i >= num; i--)
dp[i] = dp[i] || dp[i - num];
return dp[target];
}
|
目标和：给数组里的每个数字添加正负号得到target
数组和sum,目标和s, 正数和x,负数和y,则x+y=sum,x-y=s,那么x=(s+sum)/2=target
0-1背包不考虑元素顺序的组合问题:选nums里的数得到target的种数,外循环nums,内循环target倒序,应用状态方程3
1
2
3
4
5
6
7
8
9
10
11
12
| int findTargetSumWays(vector<int> &nums, int s) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if ((sum + s) % 2 != 0 || sum < s)
return 0;
int target = (sum + s) / 2;
vector<int> dp(target + 1);
dp[0] = 1;
for (int num : nums)
for (int i = target; i >= num; i--)
dp[i] += dp[i - num];
return dp[target];
}
|
完全平方数：对于一个正整数n,找出若干个完全平方数使其和为n,返回完全平方数最少数量
完全背包的最值问题：完全平方数最小为1,最大为sqrt(n),故题目转换为在nums=[1,2…..sqrt(n)]中选任意数平方和为target=n。外循环nums,内循环target正序,应用转移方程1
1
2
3
4
5
6
7
8
9
10
11
| int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int num = 1; num <= sqrt(n); num++) {
for (int i = 0; i <= n; i++) {
if (i >= num * num)
dp[i] = min(dp[i], dp[i - num * num] + 1);
}
}
return dp[n];
}
|
组合总和IV：在nums中任选一些数,和为target
考虑顺序的组合问题：外循环target,内循环nums,应用状态方程3
1
2
3
4
5
6
7
8
9
10
11
| int combinationSum4(vector<int> &nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num<=i && dp[i - num]<INT_MAX-dp[i])
dp[i] += dp[i - num];
}
}
return dp[target];
}
|
爬楼梯问题
楼梯的阶数一共为target，一次可以走的步数为nums[i]。一共有多少种走法？
考虑顺序的组合问题：外循环target,内循环nums,应用状态方程3
1
2
3
4
5
6
7
8
9
10
11
12
| public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 1; i <= target; i++){
for(int j = 0; j < nums.length; j++){
if(i>=nums[j] && dp[i - nums[j]]<INT_MAX-dp[i]){
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
|
零钱兑换2：任选硬币凑成指定金额,求组合总数
完全背包不考虑顺序的组合问题：外循环coins,内循环target正序,应用转移方程3
1
2
3
4
5
6
7
8
9
| int change(int amount, vector<int> &coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for (int coin : coins)
for (int i = 1; i <= amount; i++)
if (i >= coin)
dp[i] += dp[i - coin];
return dp[amount];
}
|
投掷骰子的方法数：d个骰子,每个有f个面(点数为1,2,…f),求骰子点数和为target的方法
分组0/1背包的组合问题：dp[i][j]表示投掷i个骰子点数和为j的方法数;三层循环：最外层为背包d,然后先遍历target后遍历点数f
应用二维拓展的转移方程3：dp[i][j]+=dp[i-1][j-f];
1
2
3
4
5
6
7
8
9
| int numRollsToTarget(int d, int f, int target) {
vector<vector<int>> dp(d + 1, vector<int>(target + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= d; i++)
for (int j = 1; j <= target; j++)
for (int k = 1; k <= f && j >= k; k++)
dp[i][j] += dp[i - 1][j - k];
return dp[d][target];
}
|
位我上者，灿烂星空；道德律令，在我心中。