当前位置：首页 > news >正文

【动态规划】多重背包问题，分组背包问题

news 2025/8/30 7:33:58

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];
}