有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
首先多重背包问题可以转换为01背包来解决,关键就是如何转换!
我们先来一种最基本的解法。
基本思想:比如第i件物品有s个,我可以把相同种类的物品的进行合并,比如我拿出两件合并出一个新的物品,我拿出三件合并出一个新的物品,以此类推,我拿出s个合并出一个新的物品。基于这种思想,我们把第i件的s个物品转换为s种体积各不相同的物品,然后在用01背包的思想,求出最优解!
代码实现:
我们只需要在遍历到第i件的时候,多加入一个for循环,遍历s个物品并且在动态转移方程中进行合并操作!我们需要注意的是,我合并出的物品体积,一定不能超过当前背包的总体积(j),不然合并是没有意义的,并且O(V*Σn[i])的算法非常耗时,我们一定要进行一定优化!
#include <iostream>
using namespace std;
int N,V;
int dp[1010];
int main()
{
scanf("%d%d",&N,&V);
int v,w,s;
for(int i=1;i<=N;i++)
{
//读入体积,价值,件数
scanf("%d%d%d",&v,&w,&s);
for(int j=V;j>=0;j--){
//注意k*v一定小于j
for(int k=1;k<=s&&k*v<=j;k++)
{
dp[j]=max(dp[j],dp[j-k*v]+k*w);//01背包一维动态方程,当前体积为j的最优解
}
}
}
printf("%d",dp[V]);
return 0;
}
这是多重背包的一道题目,用当前复杂度可以跑出来,大家多看看!
大家看到名字可能心声疑惑,二进制怎么优化呢?,其实只是借助二进制思想优化朴素解法,在朴素解法中我们需要把,每一种背包i,按个数1~s,分为不同类,形成新体积的种类,这种做法虽然剪枝优化过(k*v<=j)复杂度仍然很高,问题的关键在于怎么分,我们可不可以,在分的时候换一种算法,不再是从1分到s,并且也可以表示出,1到s,产生同样的效果!答案肯定是有的,就是用二进制思想优化,我们下面讲解这种思想。
举例,有1000个苹果,11个箱子,将1000个苹果放入11个箱子中。我想拿走n个苹果!
请问,如何放,才能保证我只拿走m个箱子,就可以带走这n个苹果呢?
解:第一个箱子放2^0,个,第二个放2的1次幂个,第三个放2的2次幂个,以此类推第11个箱子,最多能放2的10次幂,即1024个,但肯定没有那么多,所以我将剩下的苹果放在第10个箱子中。
比如我要拿出 5个苹果,我只需要拿走第1个和第3个箱子,
再比如,我要拿走10个苹果,我只需要拿走,第4个和第2个即可!
通过这种思想我们可以知道,任意的1~n的整数,我都可以通过二进制的思想,表示出来。
原理:
一个数字，我们可以按照二进制来分解为1 + 2 + 4 + 8 …… +2^n + 余数
十进制数字7,可以从二进制100,010,001做加和得到即111,001为1,010为2,100为4,也就是1、2、4,用1、2、4可以表示1~7中任意一个数。
再比如,10,可以分为1,2,4,3这个三是怎么来的呢? 3就是余数!
通过上述原理,我们可以把第i件物品的s件,按二进制思想分为1,2,4…到剩余。这样从复杂度为s,降到了(log2S)。最后的复杂度为O(V*Σlog n[i]),这样就快了许多!
实现代码:
#include <iostream>
using namespace std;
int n,m;//n个种类,m代表包总体积
int v[11010],w[11010];//v代表体积,w代表价值
int dp[2010];
int main()
{
scanf("%d%d",&n,&m);
int cnt=0;//cnt统计新的种类
for(int i=1; i<=n; i++)
{
int a,b,s;//体积,价值,数量
scanf("%d%d%d",&a,&b,&s);
//将s件用二进制转换为log2s堆
for(int k=1; k<=s; k<<=1)
{
v[++cnt]=k*a;//前++,第1种,第二种.....
w[cnt]=k*b;
s-=k;
}
if(s)//s有剩余,自立为新品种
{
v[++cnt]=s*a;
w[cnt]=s*b;
}
}
//01背包做法
for(int i=1; i<=cnt; i++)
{
for(int j=m; j>=v[i]; j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//动态转移方程和01背包完全相同
}
}
printf("%d",dp[m]);
return 0;
}
另外一种写法
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=6e3+10;
int n,m,ans;
int f[maxn];
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
//直接做二进制枚举新的物品和01背包同时写在一起
for(int k=1;k<=s;k*=2){
for(int j=m;j>=k*v;j--){
f[j]=max(f[j],f[j-k*v]+k*w);
}
s-=k;
}
if(s){//有剩余
for(int j=m;j>=s*v;j--)
f[j]=max(f[j],f[j-s*v]+s*w);
}
}
cout<<f[m];
return 0;
}
这个问题被楼天成称为"男人八题"之一,这种方法比较难理解,大家慢慢跟着我的思路,最好用笔和纸来操作,我也会用图片帮助大家理解!
首先要学习这个方法,大家一定需要学会单调队列,以及单调队列滑动窗口问题,这里我把我写的单调队列滑动窗口问题链接黏贴给大家,大家一定一定一定要先理解单调队列滑动窗口,不然后面很难跟上!
单调队列滑动窗口问题!!!
我通过朴素解法,添加了打印语句,将每一次的f数组的更新过程记录下来!
f[j]=max(f[j],f[j-k*v]+k*w);
//打印语句
printf("f[%d]=%2d f[%d]+%d=%d\n",j,f[j],j-k*v,k*w,f[j-k*v]+k*w);
控制台第一行,代表2组数据,背包总体积为9
第二行是,第一种物品,体积为2,价值为4,件数为3!
接下来就是f数组更新过程,可以看到左边那列为f[j],右边那列为f[j-kv]+kw,整条f的信息也就是动态转移方程。
我们仔细看红框中的几组数据,找出他们的相似之处!
观察第一组红框可以发现,f[9]的更新,需要f[7],f[5],f[3]
观察第二组红框可以发现,f[7]的更新,需要f[5],f[3],f[1]
同理f[5]需要f[1],f[3],更新f[3]需要f[1]。
重点来了,通过上述规律,我可以将f[9],f[7],f[5],f[3],f[1]归于一类
同理,我将f[8],f[6],f[4],f[2],f[0]归于一类!
那么为什么会得到这样的规律呢? (分析一波,走你~~~~)
首先背包总体积为9,第一件物品体积为2,那么我最多放4件,但是只有三件,所以红框的高度最多为3。
那么为什么分两类呢? 这与物品体积有关! 9,7,5,3,1对体积2取余数,结果都为1,
0,2,4,6,8对体积取余为0!
那么可以得到一般性规律我们可以分出以0~(v-1)开头的k个类
这组数据,就是以0、1开头,1就是v-1即2-1。
怎么样,妙不妙? 妙不可言呀!(完成一半啦!)
下面就要用到单调队列滑动区间的知识,如果对单调队列滑动区间不熟悉,那么很难理解,所以大家不要好高骛远,先把上面的链接看了!如果懂得单调队列滑动区间知识的我们往下看!
我们再来看这张图,上边说过类的概念,在同一类中,红框依次向下更新,像不像一个滑动区间,我需要找出,窗口内右边那列的的最大值然后赋值给f[j]。
那么如何找出窗口内的最大值呢,或者说如何维护窗口内的最大值呢?
答案就是用单调队列
这道题我们的单调队列一定是从小到大(f[1]~f[9]这个顺序更新)来维护,每次放入队列中较大元素的下标,队首永远是窗口内的最大值。如果从上一个窗格滑动到下一个窗格如果此时队首下标不在这个窗格中,我们就不能用这个队首来更新最大值,需要把队首踢出去也就是head++操作,用新的head来更新,当前窗口最大值。
有了单调队列维护,每次更新f[j]只需要一次操作!而不是三次操作!
(注意:这个较大元素是包括了f[j-kv]+kw是他们一起,而不是单个的f[j-k*v])
举例: f[0] 、f[2]、f[4]、f[6]、f[8]
此时需要更新f[8],但是f[8]是能装下3件的,所以窗口大小为3,但此时单调队列队首停在f[0],那么我就需要将f[0]出队,然后从f[2],f[4],f[6]中选出最大的作为队首,来更新!(我只是举例,实际选最大还要加上k*w)
针对单调队列,不知道大家有没有几个问题?
一、这道题用的单调队列从小到大更新,会产生什么后果呢?如何解决呢?
举例,比如我刚刚更新的f[7],然后我去更新f[9],通过上面的例子可以知道,要想更新f[9],就需要f[7],f[5],f[3],但是f[7],f[5],f[3]都已经更新过了,我们就不能在用了!(因为我是从f[1]~f[9]这么更新过来的)
(如果这个不明白,那么证明01背包问题理解不透彻,不如再看看01背包再过来!)
解决措施:我新添加一个数组g存放f数组的初始值,也就是还没有更新的f数组的值,然后将g数组用单调队列维护,每次更新f中的值我只需要从g中所对应的窗口选出最大的即可!
举例,我想更新f[8],我就从g[6],g[4],g[2]中选出最大的给f[8],就可以了!
这是顺序更新,从f[0]~f[8],红框代表单调队列维护过程,并且用了g数组!
说了这么多那么单调队列里到底存个啥呢?存窗口中最大的值,还是下标呢?
答案是下标,下标方便我们判断队首是否在滑动窗口中,并且下标好维护!
下面我们来看代码(加油胜利就在眼前!)
for(int i=1;i<=n;i++)
{
memcpy(g,f,sizeof(f));//将数组f拷贝到g中
int v,w,s;//体积、价值、件数
scanf("%d%d%d",&v,&w,&s);
//按照体积分为v类,每个类起点为0,1,....v-1
for(int j=0;j<v;j++)
{
int head=0,tail=-1;
//遍历整个类
for(int k=j;k<=m;k+=v)
{
//利用单调队列滑动窗口模板
if(head<=tail&&k-s*v>q[head]) head++;//队首元素,不在于滑动窗口,踢出队首元素
//将在滑动区间内,中最大值,也就是单调队列中队首元素
if(head<=tail) f[k]=max(g[k],g[q[head]]+(k-q[head])/v*w);//01背包动态转移方程
//如果队尾元素小于g[k],则从队尾出队
while(head<=tail&&g[k]>=g[q[tail]]+(k-q[tail])/v*w) tail--;
//g[k]入队
q[++tail]=k;
}
}
}
根据上面的过程,我们可以概况几个步骤.
1、将f数组复制到g中
2、在同一物品时,将整个背包分类
3、遍历整个类
4、判断单调队列队首元素,是否在窗口中
5、给f[k]赋值,执行动态转移方程
6、维护单调队列,g[k]+v(v是简写)与队尾元素依次比较
7、g[k]入队
代码细节讲解:
int head=0,tail=-1;
首先单调队列是一个数组,我们用两个int型变量head,和tail来维护队头和队尾
if(head<=tail&&k-s*v>q[head]) head++;//队首元素,不在于滑动窗口,踢出队首元素
解释:k-s*v>q[head] 大家知道q是单调队列,它存到是g数组的下标,当队头元素是g[q[head]],不在新的窗口中,那么需要出队,当前元素的下标为k,窗口大小为:件数x体积也就是s✖v,那么k-s✖v>q[head]时候,q[head]也就不在窗口中!(大家动手写一下就会了)
if(head<=tail) f[k]=max(g[k],g[q[head]]+(k-q[head])/v*w);//01背包动态转移方程
这条语句,就是更新f[k],就是动态转移方程!注意max()中为g[k],不是f[k]
while(head<=tail&&g[k]>=g[q[tail]]+(k-q[tail])/v*w) tail--;
我对g[k]>=g[q[tail]]+(k-q[tail])/v*w,这个不等式进行讲解。
因为每次我都需要g[k]入队,那么在入队前我要维护单调队列,如果队尾元素的值小于g[k]+v,那么需要队尾需要出队!
比如要更更新的为f[x],那么我如何比较呢?
{(x-k)/v是件数}
g[k]+(x-k)/v✖w>=g[q[tail]]+(x-q[t])/v✖w
我们对不等式进行整理,就可以得到
g[k]>=g[q[tail]]+(k-q[tail])/v✖w
到这里,单调队列优化多重背包就讲解完毕,我们也完成了"男人八题"的其中一题
我把完整代码附上:
#include<bits/stdc++.h>
using namespace std;
int n,m;//n种,背包总体积为m
const int maxn=20010;
int f[maxn],g[maxn],q[maxn];//g数组用来复制,q用来形成单调队列,存放g中元素下标
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
memcpy(g,f,sizeof(f));//将数组f拷贝到g中
int v,w,s;//体积、价值、件数
scanf("%d%d%d",&v,&w,&s);
//按照体积分为v类,每个类起点为0,1,....v-1
for(int j=0;j<v;j++)
{
int head=0,tail=-1;
//遍历整个类
for(int k=j;k<=m;k+=v)
{
//利用单调队列滑动窗口模板
if(head<=tail&&k-s*v>q[head]) head++;//队首元素,不在于滑动窗口,踢出队首元素
//将在滑动区间内,中最大值,也就是单调队列中队首元素
if(head<=tail) f[k]=max(g[k],g[q[head]]+(k-q[head])/v*w);//01背包动态转移方程
//如果队尾元素小于g[k],则从队尾出队
while(head<=tail&&g[k]>=g[q[tail]]+(k-q[tail])/v*w) tail--;
//g[k]入队
q[++tail]=k;
}
}
}
printf("%d\n",f[m]);
return 0;
}
朴素算法复杂度
O(m*Σsi),一共m种物品,每种有s件,每一种物品都要从0件算到s件,所以为求和,在乘以m件物品就是朴素算法的复杂度。
二进制优化算法复杂度:
复杂度O(mΣlogsi),因为每件物品不需要分出0~s件,只需要分出logsi件,所以复杂度为O(mΣlogsi)
单调队列优化复杂度分析:
由于每次给f[j]赋值的操作变为一次,所以不需要求和过程复杂度为O(m*n)
写到这里,多重背包问题也就彻底解决,背包问题有趣、值得深思,背后还有更深邃的数学思想,后序我会深入研究写给大家,大家多多关注,点赞,新人太需要粉丝了 ,呜呜~~我也会在算法的世界继续遨游,分享给大家有趣的题解,算法讲解,感谢大家支持!