本文主要是介绍【算法刨析】完全背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
完全背包与01背包的区别
01背包对于一个物品只能选择一次，但是完全背包可以选择任意次；
思路
和01背包类似，01背包我们只需要判断选或不选，完全背包也是如此，不同的是，对于这个物品我们在判断选后在增加一次选择的机会，直到不选，跳转至下一个物品即可；
一般代码：
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
第k次，不选的话就是它本身，选的话就是直接选择k次即可；
当然这个代码在数据稍微大一点的时候就会超出时间限制；
#include<iostream>
using namespace std;
const int N=1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;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=0;j<=m;j++){for(int k=0;k*v[i]<=j;k++){f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}}}cout<<f[n][m]<<endl;
}优化思路
上面代码会超出时间限制是因为三层循环，下面我们来把第三层循环优化掉：
f[i][j]=max(f[i][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w......f[i-1][j-k*v]+k*w)
f[i][j-v]=max( f[i][j-v],f[i-1][j-2*v]+w,f[i-1][j-3*v]+2*w......f[i-1][j-k*v]+k*w)
f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w......f[i-1][j-k*v]+k*w 不就是f[i][j-v]+w
那么我们可以得到：f[i][j]=max(f[i][j],f[i-1][j-v]+w)
这样我们不就可以不用写第三层循环了吗？
直接用：
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
优化代码：
#include<iostream>
using namespace std;
const int N=1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;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=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);}}cout<<f[n][m]<<endl;
}我们来看一下核心代码：
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);还记得01背包的代码吗？
f[i][j] = f[i - 1][j];if(j>=v[i])
f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );是不是只有（红色标记）：
f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );不同
再次优化代码：
注意：
这里我的j的大小是从小到大开始的：
01背包中，f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );对于f[j]就相当于f[i-1][j]的大小，如果从小到大遍历，那么f[i-1][j]的大小就会发现变化，那么优化后的代码就不满足我们所推导的公式，所以我们要从大到小；
类比于01背包，完全背包的公式， f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);对于这个公式如果从大到小就会改变f[i][j]的大小，不满足所推导的公式；
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e4;
int f[N];
int w[N],v[N];int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++)cin>>v[i]>>w[i];for(int i=0;i<n;i++){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m]<<endl;
}以上就是全部内容！！
这篇关于【算法刨析】完全背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
