徐州网站建设价格,网络系统软件应用与维护,专业中山建网站公司,连环画网页设计教程背包问题的种类
背包问题是在规定背包容量为j的前提下#xff0c;每个物品对应的体积为v[i]#xff0c;价值为w[i]#xff0c;从物品0到物品i中选择物品放入背包中#xff0c;找出符合某种要求的价值。
#xff08;1#xff09;背包问题种类
01背包#xff1a;每种物…背包问题的种类
背包问题是在规定背包容量为j的前提下每个物品对应的体积为v[i]价值为w[i]从物品0到物品i中选择物品放入背包中找出符合某种要求的价值。
1背包问题种类
01背包每种物品只能选择1个。完全背包每种物品可以选择无限个。多重背包每种物品最多可选s[i]个。分组背包有若干个组每组内有若干个物品每个物品只能选一次。
2递推公式
01背包dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i])完全背包dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i])多重背包dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i], dp[i - 1][j - 2 * v[i]] w[i] ... dp[i - 1][j - s[i] * v[i]] s[i] * w[i])分组背包dp[i][j] max(dp[i - 1][j], dp[i][j - v[i][k] w[i][k], ... dp[i - 1][j - s[i]*v[i][k]] s[i] * w[i][k])
3滚动数组遍历顺序 遵循原则用到上一层的信息i-1则从大到小遍历用到本层的信息i则从小到大遍历。
01背包从大到小完全背包从小到大多重背包在01背包的基础上用到i-1层信息从大到小多一层for循环选物品个数分组背包在01背包的基础上用到i-1层信息从大到小多一层for循环选物品个数
1、01背包问题
主要分为两部分状态表示和状态计算。
1. 状态表示dp[i][j] i是物品个数j是条件限制。状态表示一般从两个角度考虑分别为集合和属性。 其中集合是只考虑前i个物品不超过j的选法集合。属性值的是数量、最大值、最小值等。当要求的数到达某一个值时就要求j - v[i]到达那个相应的值时会更新这就要求设置好初始值一般会让dp[i][0]0或dp[i][0]1。
2. 状态计算 状态计算主要是集合划分分为 f(i-1, j) 所有不选第i个物品的方案和所有选择第i个物品的方案这种方式可保证不遗漏和不重复。
1不超过j的条件下对于所有不选第i个物品的方案 因为是对i从0开始按顺序遍历因此选择的是从0-i-1中的选择方案。
2不超过j的条件下所有选择第i个物品的方案 此集合包含两个部分一个是含有第i个物品另一个是不含第i个物品从0-i-1中选择的方案。含有第i个物品时表示的是物品i的体积v[i]为唯一的定量。不含第i个物品时条件就变为j - v[i]减去了第i个物品的体积在此条件下从0-i-1中选此时会有多种方案为变量。按我们的目标要求如果要找最大值就从多种方案中的一个最大值方案如果要找最小值就从多种方案中的最小值方案。两个部分相加就是我们此方案的结果。 dp[i][j]二维数组
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1010;
int dp[N][N];int main(){int n, m;int v[N], w[N];cin n m;for(int i 1; i n; i) cin v[i] w[i];for(int i 1; i n; i) {for(int j 1; j m; j) {// 当前物品重量大于背包容量时不放该物品if(j v[i]) dp[i][j] dp[i - 1][j];// 当前物品重量小于等于背包容量时在放该物品后和不放该物品之间选择一个最大价值else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]);}}cout dp[n][m] endl;return 0;
}dp[j]一维滚动数组 将dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i])改为等价式dp[j] max(dp[j], dp[j - v[i]] w[i])遍历顺序改变为从大到小通常会初始化dp[0]0或dp[o]1。
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1010;
int dp[N];int main(){int n, m;int v[N], w[N];cin n m;for(int i 1; i n; i) cin v[i] w[i];for(int i 1; i n; i) {// 从后向前遍历表示装入一个物品后剩余的可装入容量达到的最大价值for(int j m; j v[i]; j--) {dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout dp[m] endl;return 0;
}
151、【动态规划】leetcode ——2. 01背包问题C版本二维数组滚动数组
拓展应用 152、【动态规划】leetcode ——416. 分割等和子集滚动数组二维数组C版本将重量之和除以2作为背包容量找到能让背包中可装物体体积最大的装发让背包中装入物品的重量等于背包容量。 153、【动态规划】leetcode ——416. 分割等和子集滚动数组C版本思路与上一题相同分割成两个数量相近的集合最后两个集合的综合相减。 154、【动态规划】leetcode ——494. 目标和回溯法动态规划C版本分割成正数集合和负数集合背包容量为正数集合大小找到可组成正数集合大小的组合方式。 155、【动态规划】leetcode ——474. 一和零三维数组二维滚动数组C版本字符串作为物品0和1
2、完全背包问题
与01背包的区别在于同一个物品可以有无限个对同一个物品可选择多次。 状态计算时在dp[i][j]情况下 划分集合时01背包只能 划分成两个集合 而完全背包可以划分为多个集合第i个物品选择0个、1个、2个…一直到体积达到或超过j为止的多种方案其中选择0个时就相当于在0-i-1中选择的方案dp[i - 1][j]。
递推公式表达式为 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i], dp[i - 1][j - 2*v[i]] 2*w[i] ... dp[i - 1][j - n*v[i]] n*w[i])n*v[i]刚好小于等于j
现在来进行简化由上式可知dp[i][j - v[i]] max(dp[i - 1][j - v[i]], dp[i - 1][j - 2*v[i]] w[i] ... dp[i - 1][j - n*v[i]] (n-1)*w[i])对该式两端加上一个w再联立第一个式子从而得最终简化式子
dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i])
dp[i][j]二维数组
#include iostreamusing namespace std;const int N 1010;
int dp[N][N];
int v[N], w[N];
int n, m;int main(){cin n m;for(int i 1; i n; i) cin v[i] w[i];for(int i 1; i n; i) {for(int j 1;j m; j) {if(v[i] j) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i]);}}cout dp[n][m] endl;return 0;
}d[j]一维滚动数组 滚动数组的遍历顺序按照从小到大遍历。
#include iostreamusing namespace std;const int N 1010;
int dp[N];
int v[N], w[N];
int n, m;int main(){cin n m;for(int i 1; i n; i) cin v[i] w[i];for(int i 1; i n; i) {for(int j v[i]; j m; j) {// dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i])dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout dp[m] endl;return 0;}156、【动态规划】AcWing ——3. 完全背包问题二维数组一维滚动数组C版本
拓展应用
无顺序要求的题目 159、【动态规划】leetcode ——322. 零钱兑换二维数组一维滚动数组C版本注意求最小值的初始化由于不考虑顺序问题因此遍历顺序都可以dp[i][j] min(dp[i - 1][j], dp[i][j - coins[i]])。 160、【动态规划】leetcode ——279. 完全平方数二维数组一维滚动数组C版本方式同上递推公式用上完全平方数形式dp[i][j] min(dp[i - 1][j], dp[i][j - i * i] 1)。
1组合问题 组合问题遍历顺序按先背包再物品遍历 158、【动态规划】leetcode ——518. 零钱兑换 II二维数组一维滚动数组C版本零钱可以多次使用不考虑数字顺序位置关系累加计算dp[i][j] dp[i - 1][j] dp[i][j - v[i]]。
2排列问题 排列问题遍历顺序按先物品再背包遍历 158、【动态规划】leetcode ——377. 组合总和 ⅣC版本数字可以多次使用考虑数字顺序位置关系一维滚动数组累加计算dp[j] dp[j - v[i]]二维比较特别sum(dp[i][j], dp[i][j - nums[k])内层需要从0-i再遍历一次。 145、【动态规划】leetcode ——70. 爬楼梯暴力法动态规划C版本完全背包解法与题2相同也是排列问题。 161、【动态规划】leetcode ——139. 单词拆分回溯法动态规划C版本这个题比较奇特一些当满足前面的字符可以被组成并且当前单词可以有字典中组成时为dp[j] true
3、多重背包问题
多重背包是对每种物品的数量进行限制dp[i][j]的意思在第i种物品的个数为规定s[i]个的前提下背包容量为j物品体积为v[i]从物品0到物品i中选择物品可达到的最大价值。
实现方式是在01背包实现的基础上遍历时候在最内层设置一个for循环寻找从一个都不选到选s[i]个第i个物品时哪种情况取得最大价值。
dp[i][j]二维数组
#include iostream
#include algorithmusing namespace std;const int N 110;int n, m;
int dp[N][N];
int v[N], w[N], s[N];int main() {cin n m;for(int i 1; i n; i) cin v[i] w[i] s[i];for(int i 1; i n; i) {for(int j 1; j m; j) {// 一个都不选一直到选s[i]个选择一种最大价值情况for(int k 1; k s[i] j k * v[i] ; k) {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - k * v[i]] k * w[i]);}}}cout dp[n][m] endl;return 0;}
d[j]一维滚动数组
#include iostream
#include algorithmusing namespace std;const int N 110;int n, m;
int dp[N];
int v[N], w[N], s[N];int main() {cin n m;for(int i 1; i n; i) cin v[i] w[i] s[i];dp[0] 0;for(int i 1; i n; i) {for(int j m; j 0; j--) {// 一个都不选一直到选s[i]个选择一种最大价值情况for(int k 0; k s[i] j k * v[i] ; k) {dp[j] max(dp[j], dp[j - k * v[i]] k * w[i]);}}}cout dp[m] endl;return 0;}
162、【动态规划】AcWing ——4. 多重背包问题 IC版本
4、分组背包
分组背包问题是在01背包的基础上多了一个组的概念。有若干个组每组里面有若干个物品每个物品只能选择一次找到在背包容量为j的前提下从0-i组中选择物品达到背包里价值最大。
d[j]一维滚动数组
#include iostream
#include algorithmusing namespace std;const int N 110;
int n, m;
int v[N][N], w[N][N], s[N];
int dp[N];int main() {cin n m;for(int i 1; i n; i) {cin s[i];for(int j 0; j s[i]; j) {cin v[i][j] w[i][j];}}for(int i 1; i n; i) { // 遍历物品for(int j m; j 1; j--) { // 从大到小遍历背包使用i-1层信息for(int k 0; k s[i]; k) { // 遍历每组内的物品个数if(j v[i][k]) {dp[j] max(dp[j], dp[j - v[i][k]] w[i][k]);}}}}cout dp[m] endl;return 0;
}166、【动态规划】AcWing ——9. 分组背包问题C版本
