第一讲 01背包
题目
给定物品个数n,背包容量v,每个物品都有一个体积c和价值w,要求向背包中装物品使得总价值最高.
基本思路
状态表示:f(i,j)表示前i个物品试图装入一个容量为j的背包的最大价值.
边界情况:f(0,j)=0.
状态转移:f(i,j)=max(f(i-1,j),f(i,j-save[i])+value[i]). 即装或不装第i个物品
时间复杂度O(VN) 空间复杂度O(VN)
例1 hdu2602 01背包裸题
两个wa点,第一个是多组数据没有注意到,第二个是存在体积为0的情况,所以j需要从0枚举起.
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) scanf("%d",&value[i]);
for(int i=1;i<=n;i++) scanf("%d",&volume[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<=v;j++)
if(j<volume[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);
printf("%d\n",dp[n][v] );
优化空间复杂度
注意到每个状态f(i,j)只与之前的状态f(i-1,j)和f(i-1,j-save[i])有关.实际上开一个二维数组是不必要的,完全可以开一个一维数组下标为j,然后循环递推n次.
即f(j)=max(f(j),f(j-save[i])+value[i]),但是正向循环是错误的,因为之前的j-save[i]已经被新状态所覆盖,正确的做法只要反转一下顺序,逆向循环就好.
int n=read(),v=read();
for(int i=1;i<=n;i++)value[i]=read();
for(int i=1;i<=n;i++)volume[i]=read();
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=v;j>=volume[i];j--)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
printf("%d\n",dp[v] );
注意此时这个数组的意义是:容量为j的背包最多能装多少价值的物品.
遍历i个物品后,得到结果.
初始化的细节问题(满包)
01背包满包问题:给定物品个数n,背包容量v,每个物品都有一个体积c和价值w,请问恰好装满背包时最大总价值是多少.
状态表示,转移方程同理:f(j)=max(f(j),f(j-save[i])+value[i]))
但是初始条件:f(j)=-∞,f(0)=0.意义是0件物品时不可能装到除0之外的容量,-∞表示无解.
递推结束后会有很多状态都是无解,表示不能达到.
例2 luogu P1164 小A点菜 01背包满包求方案数
状态表示:f(j)表示容量为j的背包装满有几种方案.
初始条件:f(j)=0,f(0)=1
状态转移:f(j)=f(j)+f(j-save[i])
int n=read(),m=read();
for(int i=1;i<=n;i++)
save[i]=read();
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
dp[j]=dp[j]+dp[j-save[i]];
printf("%d\n",dp[m] );
一个常数优化
01背包二重循环的下限可以从Ci优化成max(V − Σ(i到n)C, Ci)
在这之前我有一个疑惑,为什么下限会是ci,这在未优化空间复杂度时是不成立的.
但是优化空间复杂度后显然成立,因为”什么都不做”就是dp[j]=dp[j].
所以转移方程就是
for(int i=1;i<=n;i++)
for(int j=v;j>=volume[i];j--)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
下面考虑原文中的优化,这个数值是仅与i有关的.
看了网上大佬的思路,意思是某些算出来的背包实际上对最终结果是没有帮助的.
最多有帮助的就是总体积减去之后每个物品的体积之和.
比如计算最后一件物品时,V-C(n-1)以下容量的背包是不可能转移到结果的.
同理,计算倒数第二件物品时,V-C(n-1)-C(n-2)以下的背包也是不可能转移到最终结果的.
int n=read(),v=read(),lim=v;
for(int i=1;i<=n;++i) value[i]=read();
for(int i=1;i<=n;++i) volume[i]=read(),lim-=volume[i];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;++i)
{
int th=max(lim,volume[i]);
for(int j=v;j>=th;--j)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
lim+=volume[i];
}
printf("%d\n",dp[v] ); 第二讲 完全背包问题
问题
完全背包问题:给定一个容量为v的背包和n种物品,每种物品有无限个且有体积Ci和价值Wi.问最多能向背包中装多少价值的物品?
naive approch
状态表示:F(i,j)仍表示对于前i种物品,背包容量为j时最多价值为多少?
初始情况:F(0,j)=0
状态转移:f(i,j)=max{f(i-1,j-kCi)+kWi} (0<=k<=j/Ci)
复杂度O(V∑V/Ci)
优化
优化1:对于Ci<=Cj,Wi>=Wj的情况,扔掉j 需要O(N^2)进行优化
优化2:基数排序,扔掉Ci>V的i,对0到V每个容量,选择Wi最大的物品. 需要O(V+N)
转化
将完全背包转化为01背包.
第一种转化,每种物品对应为V/Ci个物品
第二种转化,将第i种物品拆分成Ci*2^k,Wi*2^k的若干件物品,满足Ci*2^k<=V即可
每种物品对应log(V/Ci)个物品,优化很大.
O(VN)算法
for(int i=1;i<=n;i++)
for(int j=volume[i];j<=v;j++)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]); 这个算法与01背包空间优化后的算法,只有j的遍历顺序相反.
因为01背包倒序遍历就是为了避免一件物品被计算多次.
两层循环可以交换顺序,某些情况下带来常数优化???
第三讲 多重背包
题目
给n种物品和一个容量为v的背包,每种物品最多有num[i]件可用,每个物品都有一个体积volume[i]和价值value[i],求背包最多能装多少价值的物品?
基本算法
dp[j]表示容量为j的背包最多能装多少价值的物品.
dp[j]=max{dp[j-k*volume[i]]+k*value[i]} 0<=k<=num[i]
复杂度O(VNnum[i])
如果转换为01背包,相当于物品数为∑num[i]的01背包问题,复杂度O(V∑num[i])
二进制优化
将Mi件体积为Ci,价值为Wi的物品,可以转换为ceil(logMi)件物品:
每件物品的体积和价值都乘以一个系数,系数依次为1,2,4,8,…..,2^(k-1),Mi-(2^k-1).
其中k满足是Mi-(2^k-1)>0的最大整数
正确性:
注意到做01背包时会给出每件物品取或不取的最优情况,也即如果直接分成Mi件物品,跑完之后总会给出最优取几件的情况.
而由分成的这些物品和0(不取),可以组合成0到Mi之间的任何一个数字.按01背包跑完后,同样会给出一摸一样的最优取几件的情况.
两者是完全等效的.
复杂度
O(V∑log(Mi))
实现
对于物品num[i],volume[i],value[i]
如果num[i]*volume[i]>=V 直接按照完全背包来做这个物品即可
令k=1;
当k<num[i],时
—对物品k*volume[i],k*value[i]做01背包
—num[i]-=k;
—k<<=1
最后,对num[i]*volue[i],num[i]*value[i]做01背包
O(VN)的解法
对于基础的状态转移,使用单调队列来优化,达到O(VN)的复杂性
在优化dp的时候再去学习
例题
51nod 1086 背包问题V2 多重背包裸题
完全如上文所说,有几个需要注意的点:
1.要非常熟练完全背包和01背包的基础代码写法.
2.关于k的循环选取应该有更好的方式
int n=read(),v=read();
for(int i=1;i<=n;i++)
{
volume[i]=read();
value[i]=read();
num[i]=read();
}
for(int i=1;i<=n;i++)
{
if(volume[i]*num[i]>=v)
{
for(int j=volume[i];j<=v;j++)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
continue;
}
for(int k=1;k<num[i];k<<=1)
{
int volu=k*volume[i],valu=k*value[i];
for(int j=v;j>=volu;j--)
dp[j]=max(dp[j],dp[j-volu]+valu);
num[i]-=k;
}
int volu=num[i]*volume[i],valu=num[i]*value[i];
for(int j=v;j>=volu;j--)
dp[j]=max(dp[j],dp[j-volu]+valu);
}
printf("%d\n",dp[v] ); 以上是略微改过的代码,用了一个完全背包两个01背包.
有一个疑惑点:如果直接将volu和value左移位,会谜之wa,保存这个问题,先略.
第四讲-混合三种背包问题
问题
如果三种背包问题混合起来,即有的物品能选一次,有的物品能选多次,有的物品能选无限次,如何求解?
解法
那当然是分类讨论if else.
其实在完全背包的解法中就有这样的感觉.对于总体积超过背包体积的,按完全背包算.
实现
01背包实际上都按多重背包解即可,复杂度不会提高.而对于完全物品,设置它的数量为v/volume[i]*10,保证不会爆范围就行,这样走多重背包的时候就会直接走第一个if.
其他
原文中特别注重培养抽象出模型的能力,实际上这个能力也非常重要.在写多重背包时,调用01背包和完全背包就使用了这样的能力.
第五讲-二维费用的背包问题
问题
给一个容量为V的背包,你的负重最大只有W,然后有n种物品,每种都有若干个(0个,无限,多个),体积为volume[i],重量为weight[i],价值为value[i].问最多能装多少价值的物品,在不超过体积及负重的情况下?
解法
状态加一维
用dp[j][k]表示容量为j负重为k时的最大价值.
则dp[j][k]=dp[j-volume[i]][k-weight[i]]+value[i].
根据物品种类的不同,选择01背包,完全背包,多重背包的转移方式.
其他
常见的问题是个数限制,这个时候将个数变成第二维是个不错的选择.
除此之外,原文中说二维背包实际上类似于复整数域的一维背包,我的理解是两个维度是完全正交的,完全不相关地添加.而且用这样地方法可以实现更高维地背包.
例题 vijos 1334 NASA的食物计划
二维费用01背包,模板题
注意01背包和完全背包的遍历顺序不同,不要写错了
int v=read(),w=read(),n=read();
for(int i=1;i<=n;i++)
volume[i]=read(),weight[i]=read(),value[i]=read();
for(int i=1;i<=n;i++)
for(int j=v;j>=volume[i];j--)
for(int k=w;k>=weight[i];k--)
dp[j][k]=max(dp[j][k],dp[j-volume[i]][k-weight[i]]+value[i]);
printf("%d\n",dp[v][w] );
return 0;
第六讲-分组的背包问题
题目
有n件物品可以被放入一个容量为v的背包中,每件物品体积为volume[i],价值为value[i].此外,这些物品被分成p组,每组中的物品最多只能选一件,求背包中最多可以装多少价值的物品.
分析
对于每组物品,可以选择这组物品中某一件,或者这组中一件也不选.
是不是感觉这个东西有点像,01背包?
如果用dp(k,v)表示前k组物品最多在容量为v的背包中装多少价值,那么显然
dp(k,v)=max(dp(k-1,v),dp(k-1,v-volume[i])+value[i]),其中i遍历第k个物品集合.
实现
for(int k=1;k<=p;k++)
for(int j=v;j>=0;j–) //此处遍历顺序与物品种类有关
for(int i:part[k])
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]).
注意遍历方式一定是kji,如果是kij的话就无法保证每组只选一个了.
先j再i保证了每组内,每个体积只会被一个最优的物品访问到.
优化
这里可用第二讲完全背包中的对应优化
1.n^2遍历,将体积大价值小的物品去掉.
2.计数排序,去掉体积大于v的物品,相同体积的物品只取价值最大的.(限制物品个数大于体积的情况?)
其他
一点自己的看法
以上得思考都是基于01背包来做的,那么其他呢?
如果每组可以取无限次,每次取的物品可以不一样:分组就没有意义了,对所有物品完全背包即可.
如果每组可以取无限次,每次取的物品必须相同: 这是什么问题?想不出来,先略.
第七讲-有依赖的背包问题
有依赖的背包问题指的是如果物品j依赖于物品i, 要想选择物品j必须先选择了物品i.
一个简化的问题是:一件物品只会依赖最多一件物品,且附属品不会被依赖.
思考
首先想一下我的dp训练第19题黄金矿工.那道题里实际上一条过原点的直线上的金块会按顺序依赖.当时的解法是将一条线上的所有物品看成一组,然后将组中前方物品的值加在后方物品上.这种方法在解决链状依赖时非常有效.
如果不是链状依赖呢?比如物品2和3都依赖于物品1,这时总的情况实际上有5种:都不选,只选1,选12,选13,选123.物品有多件时情况数会成指数增长,显然枚举是不可行的.
简化后的问题
背包九讲原文中给出的方法是处理这一组物品,对每个费用只保留价值最大的情况.相当于做成了一个泛化物品(泛化物品是指某种物品给定一个费用就会返回一个价值).然后使用第六讲分组背包中的算法就可以解决.
关键的问题是怎么处理?此时一组物品中有1个主件和若干个附件,在选择主件后,每个附件都是可选可不选的,现在需要得到每个特定费用的最大价值,怎么做?
答案是,01背包. 对所有附件做一次01背包之后,再加上主件的花费和价值,就得到了这个泛化物品的所有属性.
算法
只空谈算法而不写程序是ACMer大忌!我怎么把这个忘了!
一个标准的解法是对于每个主件从dp数组copy一个tmp数组,然后让所有这个主件的附件对tmp数组做01背包.做完之后对每个值加上主件的体积和价值,求一个max.
for(int i=1;i<=n;i++)
{
memcpy(tmp,dp,sizeof(dp));
for(each attachment k of item i)
for(int j=v;j>=volume[k];j--)
tmp[j]=max(tmp[j],tmp[j-volume[k]]+value[k]);
for(int j=v;j>=volume[i];j--)
dp[j]=max(dp[j],tmp[j-volume[i]]+value[i]);
}
对每个附件做完01背包之后,tmp表示前i-1组物品和这些附件在每个体积时的最优情况.但是,如果需要tmp里的某个值,得先经过主件之后才能转移到dp中.
从dp和tmp得到dp的过程实际上也是一个01背包,只是通常的01背包是针对数组本身选或不选,而本处则是针对两个数组谁可以转移到新的dp做出的选择.
按最优状态分析一下,新的dp[j]只可能会由两个状态转移而来,一个是这一组物品任意一个都不选,即旧dp[j],另一个则是选了主件和某些附件,则由tmp转移.
这里还是很绕,多回来看一看.
更复杂的问题
复杂问题是指,主件和附件之间的依赖关变成了一棵树,所有依赖的集合是一个森林.这里假设每个物品只能依赖一件物品且不会循环依赖.
解法是,从叶子到根依次进行上述的01背包过程,就得到了这整棵树的泛化模型,森林中所有树的泛化模型都得到后,使用分组背包的算法即可解决问题.
第八讲-泛化物品
泛化物品准确来说,不是一类题目,而是一种思想.泛化物品的定义是
考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分
配给它的费用而变化。这就是泛化物品的概念。
或者
更严格的定义之。在背包容量为V 的背包问题中，泛化物品是一个定义
域为0 … V 中的整数的函数h，当分配给它的费用为v时，能得到的价值就
是h(v)。
再或者
这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0 … V ]，
给它费用v，可得到价值h[v]。
当我看到这里的时候,我真正觉得这个概念的提出者和背包九讲的作者崔添翼是一个了不起的人物.他用这样的概念,简单准确的描述了到底什么是背包,背包问题到底在干什么.
一个01背包中的物品(体积ci,价值wi),它的泛化物品模型是h(ci)=wi,h(其他)=0.
一个完全背包中的物品,它的模型是h(ci*k)=wi*k,其中k为正整数且ci*k<=V, h(其他)=0.
一个多重背包中的物品,则是h(ci*k)=wi*k,其中k<=ni且ci*k<=V, h(其他)=0.
一个互斥的物品组,h(ci)=wi,i取遍组中物品的编号,ci相同时wi取最小值,h(其他)=0
泛化物品的和
如果给定两个泛化物品a和b,现在有体积v来装这两种物品,要求获得最大价值.怎么做?
上文中有提到,将泛化物品直接使用分组背包的方法可以求解,注意泛化后每一组中互斥物品个数实际上都是v了,复杂度O(n*v*v),其中n为泛化物品个数.
如果仅仅有两个物品呢,设用体积j来装这两种物品的最大价值为dp[j]
则dp[j]=max{a(k)+b(v-k)},k取遍0到j,答案就是dp[v]
新合成的dp数组,实际上,也是一个泛化物品.
由泛化物品的性质可知,如果将两个泛化物品这样合成一个新的物品,新的物品在问题种完全可以取代原有的两个物品.
背包与泛化物品
背包问题中都会有的dp数组,处理完之后的值实际上也是一个泛化物品,是所有原有物品的和.
所以,求解背包实际上就是求得各个体积时的最优价值,得到最终的泛化物品.
带着泛化物品的思想,可以再去回头看看第六和第七讲.
第九讲-背包问题问法的变化
背包问题的一些基础问法
给定背包的体积限制,求最大价值
给定背包的体积限制,求最小价值 (max改为min)
给定背包的体积限制,求最大件数 (价值为1)(或贪心)
给定背包的体积限制,求最小件数 (贪心)
给定背包的体积限制,求最多装满多少空间(判断每个体积是否可达)
输出方案
去掉空间优化,变成二维数组
记录每个最优的子问题是由max的哪项推过来的,倒推回去即可得到是否选择某件物品
不用显示记录,倒推时比较两项即可.
输出字典序最小的方案
由于前方物品比后方物品重要,最好将子问题从前i件物品改成后i件物品.
每次倒推时,如果dp[i-1][j]与dp[i-1][j-volu]+valu并列,选择后者.
也可以不改状态表示,而是将所有物品做一个转换x=n+1-x
输出方案时转换回来即可
对某个体积求方案数
转移方程改为sum
初始条件改为dp[0][0]=1
最优方案总数
多增加一个数组mem[i][j]表示dp[i][j]最优时方案数有几种
初始条件mem[0][0]=1
状态转移(在dp转移后):if(dp[i][j]==dp[i-1][j]) mem[i][j]+=dp[i-1][j]
if(dp[i][j]==dp[i-1][j-volu]+valu) mem[i][j]+=mem[i-1][j-volu]
求次优解或第k优解
每个dp状态实际是一个有序数组,代表前k优解
转移时将dp[i-1][j]与dp[i-1][j-volu]+val进行一个merge操作,即可得到dp[i][j]
复杂度O(NVK)
一个正确的状态转移方程实际遍历了所有的解法,只不过忽略了很多非最优解
京公网安备 11010502036488号