程序员必背十大基础算法（程序员必学算法）
程序员必背十大基础算法（程序员必学算法）每件商品都有无限个！重量价值物品0115物品1320物品2430在下面的讲解中，我依然举这个例子：背包最大重量为4。物品为：
通知：我已经将刷题指南全部整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在电脑上阅读，这个仓库每天都会更新，大家快去给一个star支持一下吧！
完全背包有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。
在下面的讲解中，我依然举这个例子：
背包最大重量为4。
物品为：
重量价值物品0115物品1320物品2430
每件商品都有无限个！
问背包能背的物品最大价值是多少？
01背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序经行分析！
关于01背包我如下两篇已经进行深入分析了：
- 程序员必学算法「动态规划」：关于01背包问题，你该了解这些
- 程序员必学算法「动态规划」：01背包用滚动数组来实现
首先在回顾一下01背包的核心代码
for(inti=0;i<weight.size();i ){//遍历物品
for(intj=bagWeight;j>=weight[i];j--){//遍历背包容量
dp[j]=max(dp[j] dp[j-weight[i]] value[i]);
}
}
我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
//先遍历物品，再遍历背包
for(inti=0;i<weight.size();i ){//遍历物品
for(intj=weight[i];j<bagWeight;j ){//遍历背包容量
dp[j]=max(dp[j] dp[j-weight[i]] value[i]);
}
}
至于为什么，我在动态规划：关于01背包问题，你该了解这些！（滚动数组）中也做了讲解。
dp状态图如下：
相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。
其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？
难道就不能遍历背包容量在外层，遍历物品在内层？
看过这两篇的话：
- 程序员必学算法「动态规划」：关于01背包问题，你该了解这些
- 程序员必学算法「动态规划」：01背包用滚动数组来实现
就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一位dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）。
先遍历被背包在遍历物品，代码如下：
//先遍历背包，再遍历物品
for(intj=0;j<=bagWeight;j ){//遍历背包容量
for(inti=0;i<weight.size();i ){//遍历物品
if(j-weight[i]>=0)dp[j]=max(dp[j] dp[j-weight[i]] value[i]);
}
cout<<endl;
}
C 测试代码
完整的C 测试代码如下：
//先遍历物品，在遍历背包
voidtest_CompletePack(){
vector<int>weight={1 3 4};
vector<int>value={15 20 30};
intbagWeight=4;
vector<int>dp(bagWeight 1 0);
for(inti=0;i<weight.size();i ){//遍历物品
for(intj=weight[i];j<=bagWeight;j ){//遍历背包容量
dp[j]=max(dp[j] dp[j-weight[i]] value[i]);
}
}
cout<<dp[bagWeight]<<endl;
}
intmain(){
test_CompletePack();
}
//先遍历背包，再遍历物品
voidtest_CompletePack(){
vector<int>weight={1 3 4};
vector<int>value={15 20 30};
intbagWeight=4;
vector<int>dp(bagWeight 1 0);
for(intj=0;j<=bagWeight;j ){//遍历背包容量
for(inti=0;i<weight.size();i ){//遍历物品
if(j-weight[i]>=0)dp[j]=max(dp[j] dp[j-weight[i]] value[i]);
}
}
cout<<dp[bagWeight]<<endl;
}
intmain(){
test_CompletePack();
}
当然，虽然如果有同学想测一测究竟交换两个for循环的顺序可不可以，leetcode上还没有原题，感兴趣的同学可以去poj 或者 acwing等oj上去测一测！
我这里给出在acwing可以AC的代码。
题目地址：https://www.acwing.com/problem/content/3/
//版本一：在遍历顺序上先遍历物品，在遍历背包容量
#include<iostream>
#include<vector>
usingnamespacestd;
intmain(){
intn m;
//intw[35000] v[35000];
while(cin>>n>>m){
vector<int>w(m);
vector<int>v(m);
vector<int>dp(m 1 0);
for(inti=0;i<n;i )cin>>w[i]>>v[i];
for(inti=0;i<n;i ){//遍历物品
for(intj=w[i];j<=m;j ){//遍历背包容量
dp[j]=max(dp[j] dp[j-w[i]] v[i]);
}
}
cout<<dp[m]<<endl;
return0;
}
}
//版本二：先遍历背包容量，在遍历物品
#include<iostream>
#include<vector>
usingnamespacestd;
intmain(){
intn m;
while(cin>>n>>m){
vector<int>w(m);
vector<int>v(m);
vector<int>dp(m 1 0);
for(inti=0;i<n;i )cin>>w[i]>>v[i];
for(intj=0;j<=m;j ){//遍历背包容量
for(inti=0;i<n;i ){//遍历物品
if(j-w[i]>=0)dp[j]=max(dp[j] dp[j-w[i]] v[i]);
}
}
cout<<dp[m]<<endl;
return0;
}
}
总结
细心的同学可能发现，全文我说的都是对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
但如果题目稍稍有点变化，就会体现在遍历顺序上。
如果问装满背包有几种方式的话？那么两个for循环的先后顺序就有很大区别了，而leetcode上的题目都是这种稍有变化的类型。
这个区别，我将在后面讲解具体leetcode题目中给大家介绍，因为这块如果不结合具题目，单纯的介绍原理估计很多同学会越看越懵！
别急，下一篇就是了！哈哈
最后，又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后在问，两个for循环的先后是否可以颠倒？为什么？这个简单的完全背包问题，估计就可以难住不少候选人了。
力扣刷题指南：https://github.com/youngyangyang04/leetcode-master
这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！
@代码随想录 期待你的关注
