设计logo网站是平面设计不,工业产品设计就业,西安app开发公司排名,网站建设时设置语言选项目录
a.背包理论基础——01背包
1.二维数组的01背包表示
2.一维滚动数组表示
b. 416. 分割等和子集 - 力扣#xff08;LeetCode#xff09; a.背包理论基础——01背包
背包问题分类#xff1a; 对于面试的话#xff0c;其实掌握01背包#xff0c;和完全背包#xff…目录
a.背包理论基础——01背包
1.二维数组的01背包表示
2.一维滚动数组表示
b. 416. 分割等和子集 - 力扣LeetCode a.背包理论基础——01背包
背包问题分类 对于面试的话其实掌握01背包和完全背包就够用了最多可以再来一个多重背包。
而完全背包又是也是01背包稍作变化而来即完全背包的物品数量是无限的。
所以背包问题的理论基础重中之重是01背包
01背包的特点是有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
对于背包问题的动态规划问题一般有一维滚动数组和二维数组两种表示方式对于新手来说二维数组表示可能更直观一些这里先介绍二维数组的表示
1.二维数组的01背包表示
动态规划五部曲
1.确定dp数组及下标含义 dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 2.确定递推公式 dp[i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
那么可以有两个方向推出来dp[i][j] 1不选择第i个物品则此时背包容量和最大价值都不更新dp[i][j]由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j] 2选择第i个物品放入背包则此时背包容量减少最大价值增加dp[i][j]由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值 所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
3.dp数组如何初始化 当背包容量为零时装不进任何物品所以 dp[i][0]0当容量为j,物品编号为0时
dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。
那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。
当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。故初始化
for(int j0;jweight[0];j{dp[0][j]0;
}for(int jweight[0]; jbagweight;j){dp[0][j]value[0];
} 此时dp数组初始化情况如图所示 dp[0][j] 和 dp[i][0] 都已经初始化了那么其他下标应该初始化多少呢
其实从递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了那么 其他下标初始为什么数值都可以因为都会被覆盖。
只不过一开始就统一把dp数组统一初始为0更方便一些。 4.确定遍历顺序
从递推公式可以看出有两个遍历的维度物品与背包重量那么问题来了先遍历 物品还是先遍历背包重量呢其实都可以 但是先遍历物品更好理解。 5.举例推导dp数组
来看一下对应的dp数组的数值如图 最终结果就是dp[2][4]。
//二维dp数组实现
#include bits/stdc.h
using namespace std;int n, bagweight;// bagweight代表行李箱空间
void solve() {vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vectorvectorint dp(weight.size(), vectorint(bagweight 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j weight[0]已在上方被初始化为0// j weight[0]的值就初始化为value[0]for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];}for(int i 1; i weight.size(); i) { // 遍历科研物品for(int j 0; j bagweight; j) { // 遍历行李箱容量// 如果装不下这个物品,那么就继承dp[i - 1][j]的值if (j weight[i]) dp[i][j] dp[i - 1][j];// 如果能装下,就将值更新为 不装这个物品的最大值 和 装这个物品的最大值 中的 最大值// 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 该物品的价值构成else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}}cout dp[weight.size() - 1][bagweight] endl;
}int main() {while(cin n bagweight) {solve();}return 0;
}2.一维滚动数组表示 在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。
这就是滚动数组的由来需要满足的条件是上一层可以重复利用直接拷贝到当前层。
规五部曲分析如下 1.确定dp数组的定义 在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
2.一维dp数组的递推公式 dp[j]为 容量为j的背包所背的最大价值那么如何推导dp[j]呢
dp[j]可以通过dp[j - weight[i]]推导出来dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。也就是容量为j的背包放入物品i了之后的价值即dp[j] 此时dp[j]有两个选择一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]即不放物品i一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值
所以递归公式为
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
3.一维dp数组如何初始化 dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。 那么dp数组除了下标0的位置初始为0其他下标应该初始化多少呢看一下递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]); dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。 4.一维dp数组遍历顺序 二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。
为什么呢倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次举一个例子物品0的重量weight[0] 1价值value[0] 15 如果正序遍历
dp[1] dp[1 - weight[0]] value[0] 15
dp[2] dp[2 - weight[0]] value[0] 30
此时dp[2]就已经是30了意味着物品0被放入了两次所以不能正序遍历。
为什么倒序遍历就可以保证物品只放入一次呢
倒序就是先算dp[2]
dp[2] dp[2 - weight[0]] value[0] 15 dp数组已经都初始化为0
dp[1] dp[1 - weight[0]] value[0] 15
所以从后往前循环每次取得状态不会和之前取得状态重合这样每种物品就只取一次了。
那么问题又来了为什么二维dp数组遍历的时候不用倒序呢
因为对于二维dpdp[i][j]都是通过上一层即dp[i - 1][j]计算而来本层的dp[i][j]并不会被覆盖 5.举例推导dp数组
一维dp分别用物品0物品1物品2 来遍历背包最终得到结果如下 // 一维dp数组实现
#include iostream
#include vector
using namespace std;int main() {// 读取 M 和 Nint M, N;cin M N;vectorint costs(M);vectorint values(M);for (int i 0; i M; i) {cin costs[i];}for (int j 0; j M; j) {cin values[j];}// 创建一个动态规划数组dp初始值为0vectorint dp(N 1, 0);// 外层循环遍历每个类型的研究材料for (int i 0; i M; i) {// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for (int j N; j costs[i]; --j) {// 考虑当前研究材料选择和不选择的情况选择最大值dp[j] max(dp[j], dp[j - costs[i]] values[i]);}}// 输出dp[N]即在给定 N 行李空间可以携带的研究材料最大价值cout dp[N] endl;return 0;
} b. 416. 分割等和子集 - 力扣LeetCode
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。 思路 背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。 以上分析完我们就可以套用01背包来解决这个问题了。 01背包中dp[j] 表示 容量为j的背包所背的物品价值最大可以为dp[j]。 本题中每一个元素的数值既是重量也是价值。 套到本题dp[j]表示 背包总容量所能装的总重量是j放进物品后背的最大重量为dp[j]。 那么如果背包容量为target dp[target]就是装满 背包之后的重量所以 当 dp[target] target 的时候背包就装满了。 class Solution {
public:bool canPartition(vectorint nums) {int sum0;for(int i0;inums.size();i){sumnums[i];}if(sum%21) return false;int target sum/2;vectorintdp(10001,0);for(int i0;inums.size();i){for(int jtarget;jnums[i];j--){dp[j]max(dp[j], dp[j-nums[i]]nums[i]);// coutdp[j]dp[j]endl;}}if(dp[target]target)return true;return false;}
}; 参考代码随想录 (programmercarl.com)
