题目:
有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-k
v]+k
w,整条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-k
v]+k
w是他们一起,而不是单个的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)
写到这里,多重背包问题也就彻底解决,背包问题有趣、值得深思,背后还有更深邃的数学思想,后序我会深入研究写给大家,大家多多关注,点赞,
新人太需要粉丝了
,呜呜~~我也会在算法的世界继续遨游,分享给大家有趣的题解,算法讲解,感谢大家支持!