今天老夫就把完全背包的底裤给你扒出来瞅瞅!!!
来我房里有些好康的,来看看完全背包的底裤
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。
在下面的讲解中,我依然举01背包的底裤里面的这个例子:
背包最大重量为4。
物品为:
每件商品都有无限个!
问背包能背的物品最大价值是多少?
01背包和完全背包唯一不同就是体现在遍历顺序上,所以本文就不去做动规五部曲了,我们直接针对遍历顺序经行分析!
首先再回顾一下01背包的核心代码:
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
我们知道01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:
// 先遍历物品,再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
至于为什么,我在01背包问题中也做了讲解。
这里需要注意j的起点,考虑放入当前物品的前提是当前物品的大小没有超过当前背包容量的大小,对于那些容量小于当前物品大小的状态来说,就维持旧状态即可,等于不选择当前物品
dp状态图如下:
完全背包先介绍到这,因为之前已经写过关于完全背包的文章了,文章链接放在下面:
LintCode 440 · 背包问题 III—完全背包问题
leetcode 279. 完全平方数----完全背包的套路
leetcode 322. 零钱兑换----完全背包套路解法详细再探
双重for循环遍历顺序再探
其实还有一个很重要的问题,为什么遍历物品在外层循环,遍历背包容量在内层循环?
这个问题很多题解关于这里都是轻描淡写就略过了,大家都默认 遍历物品在外层,遍历背包容量在内层,好像本应该如此一样,那么为什么呢?
难道就不能遍历背包容量在外层,遍历物品在内层?
看过这篇的话:01背包问题就知道了,01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一位dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。
在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序同样无所谓!,二维不用提更加无所谓
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环,遍历背包容量在内层循环,状态如图:
遍历背包容量在外层循环,遍历物品在内层循环,状态如图:
看了这两个图,大家就会理解,完全背包中,两个for循环的先后循序,都不影响计算dp[j]所需要的值(这个值就是下标j之前所对应的dp[j])。
先遍历背包再遍历物品,代码如下:
// 先遍历背包,再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
C++测试代码
1.先遍历物品再遍历背包容量的版本
class Solution {
public:
int backPackIII(vector<int>& A, vector<int>& V, int m)
{
int size = A.size();//物品个数
vector<int> dp(m + 1, 0);
for (int i = 0; i < size; i++)
{
for (int j =A[i]; j <= m; j++)//注意j起点值,从小到大遍历
{
dp[j] = max(dp[j], dp[j - A[i]] + V[i]);
}
}
return dp[m];
}
};
2.先遍历背包容量再遍历物品的版本
class Solution {
public:
int backPackIII(vector<int>& A, vector<int>& V, int m)
{
int size = A.size();//物品个数
vector<int> dp(m + 1, 0);
for (int j = 0; j <= m; j++)
{
for (int i = 0; i < size; i++)
{
//因为这里把物品遍历放在内侧,因此这里需要做可否放进背包的判断
if (j >= A[i]) dp[j] = max(dp[j], dp[j - A[i]] + V[i]);
}
}
return dp[m];
}
};
总结
细心的同学可能发现,全文我说的都是对于纯完全背包问题,其for循环的先后循环是可以颠倒的!
但如果题目稍稍有点变化,就会体现在遍历顺序上。
如果问装满背包有几种方式的话?那么两个for循环的先后顺序就有很大区别了,而leetcode上的题目都是这种稍有变化的类型。
这里涉及到了组合数和排列的区别
这里先不做解释,后续马上赶出这方面的文章
最后再啰嗦一下,稍微总结一下完全背包需要的注意事项
1.对完全背包的一维和二维dp而言,改变其双重for循环的顺序不会产生影响
2.一维dp下,内层循环,即物品容量对应的遍历顺序是从小到大
3.一维dp下,一般都是物品做外层循环,此时要注意内层循环j的起点是当前对应物品i的大小
相关文章
- 大数据应用日志采集之Scribe演示实例完全解析
- ImageLoader_ _Universal-Image-Loader完全解析(一)之介绍与使用详解
- 蚂蚁金服寒泉子:JVM源码分析之临门一脚的OutOfMemoryError完全解读
- JVM源码分析之Jstat工具原理完全解读
- java 11 完全支持Linux容器(包括Docker)
- 完全背包问题(DP 逐渐优化*3)
- Ubuntu18.04完全卸载vscode
- hadoop 完全分布式集群搭建
- oracle 11g客户端如何完全卸载
- Python编程语言学习:判断两个列表是否对应完全相等(巧解输出是一摸一样的列表数据,但就是不相等)
- 【华为OD机试】1050 - 完全数计算
- 智能优化算法应用:基于麻雀搜索算法与非完全beta函数的自适应图像增强算法 - 附代码
- 完全卸载mysql免安装版
- Linux 没有 my.cnf 解决方案文件完全我自己的整个教程很多口才
- INFO JobScheduler: Added jobs for time 1524468752000 ms/INFO MemoryStore: Block input-0-1524469143000 stored as bytes in memory/完全分布式 ./bin/run-example streaming.NetworkWordCount localhost 9999无法正常运行
- 【LeetCode】279. 完全平方数