Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
题目:多重背包问题
题解:
与完全背包问题不同的是，每种东西都是有限件，前两种状态就不再过多赘述，有疑问的uu们可以去看看这篇文章完全背包，第三种状态我们直接枚举即可：当能拿下k个物品时，与不拿k件物品去最大值。
代码实现:
#include<iostream> #include<algorithm> using namespace std; const int N=1100; int v[N],s[N],w[N],f[N][N]; int main() { int n=0,V=0; cin>>n>>V; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]>>s[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=V;j++) { for(int k=0;k*v[i]<=j&&k<=s[i];k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k); } } cout<<f[n][V]; }
优化：
这种做法虽然简单易懂，但时间复杂度为n^3，很容易就TLE了，所以我们必须优化一下。
这里有利用了一下快速幂（背增）的思想，不知道的uu们听我细说：
任何一个正整数都可以由二进制来表示（废话，那么我们要取得价值是不是也可以由二进制表示呢？
例如 我们有 1 2 4价值得东西，那我们就可以由这三个东西凑出0~7之间任何一个数
（由3个物品的表示凑出了7个情况），效率就高了
假设我们要凑0~9的任何一个数呢，那么1 2 4就无法表示了，我们可以给这区间加上一个2，是不是就可以表示0~9之间的任何一个情况了呢。
换到这题来看，数量为s的物品可以拆分为log s 个东西，就可以枚举出s个物品的情况，对应的价值乘上倍数k即可满足上面所说情况，所以对应的问题就变成了01背包问题
代码实现:
#include<iostream> #include<algorithm> using namespace std; const int N=110000000; int v[N],s[N],w[N],f[N][N]; int solution2() { int n=0,V=0; cin>>n>>V; int cnt=0; int k=1; for(int i=1;i<=n;i++) { int a=0,b=0,s=0; cin>>a>>b>>s; int k=1; while(k<=s) { v[++cnt]=a*k; w[cnt]=b*k; s-=k; k*=2; } if(s>0) { v[++cnt]=s*a; w[cnt]=s*b; } } n=cnt; for(int i=1;i<=n;i++) { for(int j=V;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); } cout<<f[V]; }
题目:分组背包问题
题解：
这题与完全背包问题也十分的相似，就是将一件物品无限拿，变成了一组物品挑一个。
代码实现:
#include<iostream> #include<algorithm> using namespace std; const int N=110; int v[N][N],w[N][N],s[N],f[N]; int main() { int n=0,m=0; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>s[i]; for(int j=0;j<s[i];j++) { cin>>v[i][j]; cin>>w[i][j]; } } for(int i=1;i<=n;i++) { for(int j=m;j>=0;j--) { for(int k=0;k<s[i];k++) { if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout<<f[m]; }
完结撒花：
🌈本篇博客的内容【动态规划：多重背包问题，分组背包问题】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
