青岛企业网站开发,wordpress jnews,帝国网站如何做中英文切换,聊城网络科技有限公司大家好#xff0c;今天 给大家讲解01背包问题
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]#xff0c;价值是w[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。 01背包问题是典型的动态规划问题#xff0c;我们拿葡萄矿泉水和西…大家好今天 给大家讲解01背包问题
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]价值是w[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 01背包问题是典型的动态规划问题我们拿葡萄矿泉水和西瓜举例子 这道题确实可以用暴力来做但凡这给的数是10的七次方你咋办
今天就教你们可以轻松拿捏这道题的方法DP动态规划
要想要解出来这道题咱们得先列一个表格 然后咱们的每个表格都要填写该表格所在列的背包容量最多可以在所在行的物品及以上所获得的价值总和最多能有多少
你是不是听蒙圈了
那你就蒙圈吧 没有关系下面我给你放一张图你就明白了 看懂了吧这回还没看懂我真没办法了私信我吧 首先来看第零行 肯定都是零嘛第零行是空气价值为0无论如何肯定总价值是0 接下来看第零列很明显由于背包大小为0装不了任何东西所以都填0. 我们最终要求的答案在第六列第三航。 接着问题来了第一列第一行的单元格怎么填 很简单葡萄的重量是2背包大小只有1连葡萄的大小都不够所以填0
接下来看第一行葡萄的重量是2从第二列开始所有背包的重量都≥2葡萄的价值为3所以第一行的第2-6列均为3. 接下来看第二行很明显第二行的第1、2个背包的重量不够矿泉水的重量3所以它们的最优解全部继承于上方的单元格 接下来填写第二行第三列的单元格该列的背包容量为3葡萄和矿泉水都可以被其装进去那么我们该比较了
装完葡萄之后就不可以再装其他物品了装葡萄的最优解为葡萄的价值3.
装矿泉水之后也不能装其他东西了所以装矿泉水的最优解为矿泉水的价值5.
53所以这里应该填写5. 二行四列可以只装葡萄或只装矿泉水或只装西瓜西瓜在第三行才会考虑所以这里不考虑西瓜的情况因为这是01背包问题01的意思是一个物品装的数量只有0和1所以装两个葡萄是不可能的所以也填5. 接着看二行的第五列这一列背包容量达到了5可以同时容纳葡萄和矿泉水 所以这一格填8.
第六格同样填8. 接下来看第三行这一行会考虑西瓜第1-3列由于不够装西瓜所以直接继承第二行的结果
第四列装完西瓜后没地方放别的东西了所以价值是665所以填6
第五列装完西瓜同样不能放别的东西68所以填写8. 最后三行六列便是我们最终的答案。 这一格放西瓜后还有6-42的位置正好放一个葡萄。这种方案的总价值是6399比8大。
所以这一格填写9。 最后的答案便是9了。
而我们刚刚的表格再编程中可以用一个二维数组dp来表示。
总结一下思路 状态定义设dp[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。 状态转移方程 不选第i件物品dp[i][j] dp[i-1][j]选择第i件物品前提是j w[i]dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 初始化 dp[...]0即没有物品时价值都为0。 目标dp[n][W]也就是表格的最后一行最后一列 然后上模板代码
#include iostream
#include vector
using namespace std;int main() {int n, W; // n是物品个数W是背包容量cin n W;vectorint w(n 1), v(n 1); // w是重量数组v是价值数组for (int i 1; i n; i) {cin w[i] v[i];}vectorvectorint dp(n 1, vectorint(W 1, 0));// 动态规划填表for (int i 1; i n; i) {for (int j 0; j W; j) {if (j w[i]) {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]);} else {dp[i][j] dp[i - 1][j];}}}cout dp[n][W] endl; // 输出最大价值return 0;
}但是这个代码有一个地方还可以优化空间上可以只用一维数组dp[j]来存储上一行的结果这样可以将空间复杂度从O(nW)降低到O(W)。
vectorint dp(W 1, 0);
for (int i 1; i n; i) {for (int j W; j w[i]; j--) {dp[j] max(dp[j], dp[j - w[i]] v[i]);}
}
cout dp[W] endl;注意一下第二种写法中一维数组的实现中内层循环需要倒序进行以确保每次计算使用的是上一轮的结果。
好了这一篇博客就写到这里求点赞收藏关注 你们的支持就是我更新的最大动力
