没有公司网站如何做推广,汽车销售管理系统,微客通达推广引流,科威网络做网站怎么样文章目录动态规划背包问题01背包抽象出求解目标尝试进程子问题拆分基本情况根据拆分过程定义dp数组与转移方程遍历顺序与状态压缩模板归纳题目应用变种提升组合问题多维01背包有特殊限制的01背包完全背包打家劫舍股票系列子序列类数位dp动态规划
背包问题
01背包
有C0-Cx件物…
文章目录动态规划背包问题01背包抽象出求解目标尝试进程子问题拆分基本情况根据拆分过程定义dp数组与转移方程遍历顺序与状态压缩模板归纳题目应用变种提升组合问题多维01背包有特殊限制的01背包完全背包打家劫舍股票系列子序列类数位dp动态规划
背包问题
01背包
有C0-Cx件物品每个物品价值对应为V0-Vx有容量为N的背包问背包能够装的最大价值。
由于每件物品只有装与不装两个状态因此称为01背包。
抽象出求解目标
目标C0-Cx可选价值V0-Vx容量为N能够装下的最大值。
尝试进程子问题拆分
子问题拆分 假设Cx物品选了那么问题缩减为求解 C0-Cx-1可选价值V0 - Vx-1容量为N-Vx能够装下的最大值。 假设Cx物品不选那么问题缩减为求解 C0-Cx-1可选价值V0 - Vx-1容量为N能够装下的最大值。
基本情况
很显然每件物品我们都可以按照上边的想法进行拆分求解。 当容量为0价值为0。
根据拆分过程定义dp数组与转移方程
定义dp[i][j]为物品0-i任意取放进容量为j的背包中能够装的最大重量。
转移方程dp[i][j] max(dp[i - 1][j], dp[i - 1][j - value[i]]);
遍历顺序与状态压缩
dp[i][j]依赖它的上边和左上边的数据结果因此遍历顺序自上而下自左而右。
滚动数组由于每个数据只依赖上一行两个数据的结果因此可以使用滚动数组来更新dp数组由于需要的是左上方的数据和上方的数据因此对于背包容量我们逆序遍历时遍历到某个位置时此时的滚动数组就保留了左上和上的结果; 即dp[j] max(d[j], dp[j - value[i]]);
模板归纳
枚举每个物品逆序遍历背包递推公式为dp[j] max(d[j], dp[j - value[i]]);
题目应用 子集就是每个元素选或不选最后构成的一种组合。计算数组的总和为sum如果给定背包容量为sum / 2 能够装满那么就存在否则不存在。 bool canPartition(vectorint nums) {int sum accumulate(nums.begin(), nums.end(), 0);if (sum 1) return false; // 如果sum为奇数必不可等分int target sum 1; // 最终要找的组合它的累计和是nums累计和的一半。vectorint dp(target 1, 0);for (int num : nums) {for (int j target; j num; --j) dp[j] max(dp[j], dp[j - num] num);}return dp[target] target;
}变种提升
组合问题
01背包还可以用于计算装满容量为N的物品的组合数。 n个数每个数可以是正负两种状态不过这里要求的是组合数。
首先由于符号未定我们的物品是不确定的。 但是元素总和是确定的sum 假设加法总和为x所有元素总和为sum那么减法元素总和为sum - x。 target x - (sum - x) 2x - sum x (sum target) / 2
sum和target都是已知的。
因此也就是问题可以转为装满容量为x的背包的方法数。 这样就只用考虑正数。
设dp[i][j]表示0-i元素任意选装满j的方法数 假设i选择 dp[i][j] dp[i - 1][j - nums[i]] 假设i不选 dp[i][j] dp[i - 1][j]
总方法数 dp[i][j] dp[i - 1][j - nums[i]] dp[i - 1][j]
状态转移方程与01背包几乎一致考虑滚动数组压缩 dp[j] dp[j - nums[i]] dp[j] 进一步 dp[j] dp[j - nums[i]]
此外注意求方法数时容量为0方法数为1即都不选!!!。 int findTargetSumWays(vectorint nums, int target) {int sum accumulate(nums.begin(), nums.end(), 0);if (abs(target) sum) return 0;if ((target sum) % 2) return 0;int bagSize (target sum) 1;vectorint dp(bagSize 1);dp[0] 1;for (int num : nums) {for (int j bagSize; j num; --j) {dp[j] dp[j - num];}} }return dp[bagSize];多维01背包 同样是子集问题每个元素选或者不选两种情况所不同的时有0和1两方面的限制即背包容量的维度是2维的。
dp[i][j][k]表示0-i物品任意选0的容量为j1的容量为k能够装的物品数。 子情况拆分 第i个选品如果选假设第i个物品0的个数为cnt0i、1的个数为cnt1i。 dp[i][j][k] dp[i - 1][j - cnt0i][cnt1i] 1; 第i个物品如果不选 dp[i][j][k] dp[i][j][k];
转移方程和01背包一致只依赖上方和左上方可以逆序遍历背包容量来做成滚动数组形式;
int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint(n 1, 0));for (const string str : strs) {int cntOne 0;for (char c : str) cntOne c - 0;int cntZero str.size() - cntOne;for (int i m; i cntZero; --i) {for (int j n; j cntOne; --j) {dp[i][j] max(dp[i][j], dp[i - cntZero][j - cntOne] 1);}}}return dp[m][n];
}有特殊限制的01背包 这道题也是0、1背包但是物品有主件和附件之分每个主件可以有0,1或者2个附件附件必须依赖主件。
有主附之分的物品是无法直接应用01背包模板的我们需要把元素进行组装。
具体而言一个元素的价格有四种可能主件主件附件1主件附件2主件附件1附件2。
相应的也需要把物品的价值即满意度进行组装
注意点 1、从示例2可以看出行号为物品编号附件可以出现在主件前因此先用prices和values先把数据保存下来。 2、主件价格为0可以直接跳过 3、遍历每个主件时将它与附件进行组合主件主件附件1主件附件2主件附件1附件2。 4、应用背包模板逆序遍历背包容量。 5、输入都除10可以降低时空复杂度但需要注意后边输出时乘回来。
#include bits/stdc.h
#include vector
using namespace std;int main() {int N, m;cin N m;N / 10;vectorvectorint prices(m 1, vectorint (4)), values (m 1, vectorint (4));// prices[i]3个元素分别为i号主件价格i号主件的附件1价格i号主件的附件2价格for (int i 1; i m; i) {int v, p, q;cin v p q;v / 10;p * v;if (q 0) {// 0 : 主件prices[i][0] v;values[i][0] p;} else {if (prices[q][1] 0) {// 1 : 附件1prices[q][1] v;values[q][1] p;} else {// 2 : 附件2prices[q][2] v;values[q][2] p;}}}vectorint dp(N 1);for (int i 1; i m; i) {if (prices[i][0] 0) continue;int p1 prices[i][0], p2 p1 prices[i][1], p3 p1 prices[i][2], p4 p2 p3 - p1;int v1 values[i][0], v2 v1 values[i][1], v3 v1 values[i][2], v4 v2 v3 - v1; for (int j N; j p1; --j) {dp[j] j p1 ? max(dp[j], dp[j - p1] v1) : dp[j];dp[j] j p2 ? max(dp[j], dp[j - p2] v2) : dp[j];dp[j] j p3 ? max(dp[j], dp[j - p3] v3) : dp[j];dp[j] j p4 ? max(dp[j], dp[j - p4] v4) : dp[j];}}cout dp[N] * 10 endl;return 0;
}
完全背包
打家劫舍
股票系列
子序列类
数位dp
