动态规划——多重背包问题
聪明人都会点进来学习!!动态规划看这一篇就够了!!!本文详细讲解了动态规划的核心思路(配有图片),还以经典问题——多重背包问题为例,先从基础解法开始讲解思路,再一步步优化(特别是二进制优化),带有完整代码(有详细注释),对于难以理解的地方还会举例讲解,还会和01背包问题对比思考,赶紧点进来学习吧!!!
写在前面
由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●)
如果没看过我前面关于01背包问题(良心正解)和完全背包问题(良心正解)的宝宝可以先去看看,可以让你对动态规划的理解更透彻
DP核心思路
多重背包问题
题目
思路
重要变量说明
f[][[]
:用于状态表示;
w[]
:记录每个物品的价值;
v][]
:记录每个物品的体积;
cnt[]
:记录每个物品的数量;
- 定义二维数组
f[][]
,其中f[i][j]
表示在前i
个物品,背包容积为j
的限制下所能装下的最大价值。这里的f[i][j]
就是做法的集合,f[i][j]
的值就是最大价值即属性。 - 从
i=1
开始枚举,对于第i
个物品,都有一定数量的选择:- 如果不选第
i
个物品,那么状态转移方程为f[i][j]=f[i-1][j]
- 如果选择第
i
个物品一次,那么状态转移方程为f[i][j]=f[i-1][j-v[i]]+w[i]
......
- 如果选择第
i
个物品cnt[i]
次(即每个物品的最大数量),那么状态转移方程为f[i][j]=max(f[i-1][j-cnt[i]*v[i]]+cnt[i]*w[i]
(前提是不超过当前背包的容积)
- 如果不选第
- 我们因为要求最大价值,所以对上面两种情况去
max
即可。
代码(不优化)
二维数组
#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],f[N][N],cnt[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>cnt[i];
for(int i=1;i<=n;i++) //i表示当前枚举的物品,从第1个物品开始枚举,直到第n个
for(int j=1;j<=m;j++) //j表示当前枚举的容积
for(int k=0;k<=cnt[i] and k<=j/v[i];k++) //从0(0表示不选这个物品)开始枚举,并且保证j永远大于k*[i]
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout<<f[n][m]<<endl;
return 0;
}
一维数组
二维数组优化到一维数组的具体思路和前面我写的题解思路一模一样,不懂的宝宝可以去看——>01背包问题或者完全背包问题(良心正解)
#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],f[N],cnt[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>cnt[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=0;k<=cnt[i] and k<=j/v[i];k++)
f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
cout<<f[m]<<endl;
return 0;
}
思考
聪明的你一定发现了这个问题和01背包问题非常像,如果我们把数量不止一个的物品拆成n
个相同的物品(n
是该物品的数量)。即如果一个物品的数量是n
(n
>1),那么将其看成是n个物品,只不过他们的体积和价值都一样)
#include<iostream>
using namespace std;
const int N=2e6+10;;
int v[N],w[N],f[N];
int main()
{
int n,m;
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,c,k=1;
cin>>a>>b>>c;
while(k<=c)
{
v[++cnt]=a;
w[cnt]=b;
k++;
}
}
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}
经过实测,两者的运行时间貌似差不多
终极优化(二进制优化)
我们发现这个代码运行的还是很慢,时间复杂度是 O ( n 3 ) O(n^3) O(n3),这让人难以接受,聪明的你就想办法,想啊想,终于你灵光一现,发现了一种优化方法。
思路
对于上面的思考,虽然可以把多重背包问题拆成01背包问题,但是一个一个数的去拆解太慢了,聪明的你想到每一个数都可以用二进制来表示,所以我们可以把每个物品的数量n
拆解成一些数(a1,a2,a3...at
),而这些数的组合可以表示1-n
中的任意一个数。
我们以11为例,我们把11拆解成1,2,4,4这四个数,我们可以发现1-11中的任意一个数都可以用这些数的组合来表示。
那么我们怎么拆解才能得到这些数呢
int a,b,c,k=1;
cin>>a>>b>>c;
while(k<=c)
{
v[++cnt]=k*a;
w[cnt]=k*b;
c-=k;
k*=2;
}
if(c)
{
v[++cnt]=c*a;
w[cnt]=c*b;
}
**至于为什么可以这么拆解,以及这样拆解为什么一定对,相关的数学证明我就不写了,写了也没人看。 **
代码
#include<iostream>
using namespace std;
const int N=2e6+10;;
int v[N],w[N],f[N],cnt[N];
int main()
{
int n,m;
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,c,k=1;
cin>>a>>b>>c;
while(k<=c)
{
v[++cnt]=k*a;
w[cnt]=k*b;
c-=k;
k*=2;
}
if(c)
{
v[++cnt]=c*a;
w[cnt]=c*b;
}
}
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}
写在最后
如果你觉得我写题解还不错的,请各位王子公主移步到我的其他题解看看
数据结构与算法部分(还在更新中):
- Linux部分(还在更新中):
✨🎉总结
“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”
如果有错误❌,欢迎指正哟😋
🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)