DP动态规划学习记录(四)——完全背包
❤作者:那些年丶我们逃过的课
❤博客主页:那些年丶我们逃过的课的博客_CSDN博客-c++题目,c++学习记录,c++小游戏领域博主
❤码云gitee:我的码云 - Gitee.com
❤期待你的关注,如果觉得还可以的话,可以点赞评论支持一下,每个评论我都会回访的🎉
我们已经知道了,01背包的一维dp代码如下:
详情讲解请看:DP动态规划入门学习记录(三)——01背包_那些年丶我们逃过的课的博客-CSDN博客
#includeusing namespace std;int main(){ int a,b;//a为背包载重,b为物品个数 int w[1005],v[1005]; int f[1005]={0};//定义dp数组并初始化为0 cin>>a>>b; for(int i=1;i>w[i]>>v[i]; for(int i=1;i=w[i];j--) {f[j]=max(f[j],f[j-w[i]]+v[i]); }} cout<<f[a]; return 0;}
在二重循环时,我们从后往前逆序更新数组,就是为了让每个物品只加一次。
而完全背包则是不限放入个数,那么将01背包的二重循环的逆序更新数组改成正序更新数组,那么就可以达到完全背包的要求,放入尽可能多的东西。
所以如果学会了01背包的一维dp,完全背包就很简单了。
DP代码
#includeusing namespace std;int main(){long long a,b;//a为背包载重,b为物品个数long long w[10005],v[10005];long long f[10005]={0};//定义dp数组并初始化为0cin>>a>>b;for(long long i=1;i>w[i]>>v[i];for(long long i=1;i<=b;i++)//物品遍历{for(long long j=w[i];j<=a;j++)//背包重量遍历{f[j]=max(f[j],f[j-w[i]]+v[i]); }}cout<<f[a];return 0;}
如果不知道01背包的滚动数组做法,可以先看:DP动态规划入门学习记录(三)——01背包_那些年丶我们逃过的课的博客-CSDN博客