> 文档中心 > DP动态规划学习记录(四)——完全背包

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博客

2022.5.6
13:59