程序设计竞赛背包问题-多重背包

王瑞康·山东大学
2016-02-06
阅读数2800

引言

本节通过多重背包问题,巩固上节内容的同时,进一步介绍动态规划中算法复杂度的分析,以及一些空间优化的技巧。

基本模型

现要把N种物品装进一个大小为M的背包,第i种物品有a[i]个可以使用,每一个大小为w[i],价值为v[i]。那么这个背包能装下物品的最大价值是多少?

模型分析

01背包可以看做是多重背包的一个特例,当多重背包中每种物品都仅有一个时,就退化为了01背包。自然,我们也可以用类似的方法来考虑这个问题。

我们还是先考虑第n种物品,与之前01背包不同的是,现在我们有a[n]+1种决策:即不用第n种物品、用一个、用两个……一直到用a[n]个。如果我们选择使用k个,那么将获得v[n]*k的价值,背包剩余空间为m-k*w[n]。接下来我们要用前n-1种物品,填大小为m-k*w[n]的背包,尽量获得最大的价值。

所以我们依然用f(i,j)来表示用前i种物品,填大小为j的背包,所能获得的最大价值。

由上面的分析可以整理得下面的公式:

\(f(n,m) = \mathop {\max }\limits_{k = 0}^{a[n]} \{ \matrix{ {v[n]*k + f(n - 1,m - w[n]*k)} & {m \ge w[n]*k} \cr } \} \)

 

同理可以推广到任意的f(i,j),此时的决策为第i件物品要使用多少个,读者可以尝试自己写出一般的状态转移方程。

\(f(i,j) = \mathop {\max }\limits_{k = 0}^{a[i]} \{ \matrix{ {v[i]*k + f(i - 1,j - w[i]*k)} & {j \ge w[i]*k} \cr } \} \)

边界条件依然是f(0,...)=0。

具体实现

for(j=0;j<=m;j++) f[0][j]=0;
for(i=1;i<=n;i++)
       for(j=0;j<=m;j++)
       {
              f[i][j]=f[i-1][j];      //不使用第i种物品
              for(k=1;k<=a[i];k++)           //用k枚举第i种物品使用的数量
              {
                     if(w[i]*k>j) break; //如果使用k个已经装不下了,也就不需要继续放更多的第i种物品了
                     tmp=v[i]*k+f[i-1][j-w[i]*k];
                     if(tmp>f[i][j]) f[i][j]=tmp;
              }
       }//f[n][m] is the answer

算法复杂度分析

关于时空复杂度的详细定义,由于篇幅有限,这里便不展开介绍了。如果感兴趣的话,可以翻阅《算法导论》或者在网上查找相关资料,想必可以得到满意的答案。这里仅仅简要的介绍如何分析动态规划的时空复杂度。

首先来分析时间复杂度,简而言之就是每一条语句总执行次数的规模。在本例中,我们用外层i、j两层循环,计算所有的状态,复杂度为O(n*m)。在算每一个状态时,都需要用内层k的循环,枚举每一种决策,选取一个最优值。每种物品大小最小是1,也就是说最多选取m个,所以这里的复杂度为O(m)。

状态的规模为O(n*m),计算每一个状态的复杂度为O(m),所以总的时间复杂度为两者的乘积\(O(n{m^2})\)

接下来考虑空间复杂度,也就是占用的内存空间大小的规模,通俗的讲就是开了多大的数组。本例中用二维数组存储每一个状态,空间复杂度自然就是O(n*m)。

时间优化

在这里简单地为读者介绍一种时间优化的方法——转化为01背包。

直观地来看,第i种物品最多可以用a[i]个,那就把它们当做是a[i]个不同的物品做01背包就可以了。但这样直接拆分成a[i]个同样的物品,并不会带来时间上的优化。

稍做分析便可以知道,拆成a[i]的同样的物品,虽然答案同样是正确的,但却带来了大量的冗余。x件物品每一件取或不取,总共有2^x种可能性,但因为每件物品都一样,最终其实只表示了x+1种不同的情形,即不用、用1个…用x个。很自然地便可以想到,我们是否可以使用2进制的方式来进行拆分呢?

假如说某种物品有7个可用,我们便可以把其中的4个、2个、1个分别绑做一捆作为三个不同的物品,这样只用3个物品就可以表示出原来的8种情况。

当a[i]等于2^x-1的时候,按如上方式拆成1、2、...、2^(x-1)即可。但如果2^x-1

如果不用第x+1个物品,可以表示出0到2^x-1的所有情况;

如果使用最后一个物品,则可以表示y到2^x-1+y即y到a[i]的所有情况。

两者合在一起便能表示0到a[i]的所有可能。

简而言之,用1、2、4、...、2^(x-1)和y,就可以组合出0到a[i]之间的所有数字。

于是乎问题便转化为了一个更为简洁的01背包,此时背包中的物品个数为\(\sum\limits_{i = 1}^n {(\left\lfloor {{{\log }_2}a[i]} \right\rfloor + 1)} \),背包大小仍然为M。

空间优化

在现在的ACM竞赛中,往往很少会用到空间优化的技巧,题目的空间限制往往非常宽容。但这并不意味着空间优化的手段就不重要。接下来将结合本例,介绍下空间优化的一般方法。

一个动态规划算法的核心就是状态转移方程,大多数的优化都是利用状态转移方程的特殊性质。我们先来观察一下本例中的方程:

\(f(i,j) = \mathop {\max }\limits_{k = 0}^{a[i]} \{ \matrix{ {v[i]*k + f(i - 1,j - w[i]*k)} & {j \ge w[i]*k} \cr } \} \)

不难发现,所有的f(i,...)只与f(i-1,...)有关。

我们动态规划求解所有状态的过程就像填表格一样,第i行就是f(i,...)。那么我们首先利用边界条件在第0行填满0,接下来用第0行的值算出第1行的值,以此类推,直到把前n行都填满。

因为第i行的值只与第i-1行的值有关,也就是说只有在填第i行时,第i-1行才是有用的。一旦第i行填好,开始算第i+1行,那么第i-1行再无任何用处(至少对于本例的问题是没有用了)。既然这样,我们何必还把它们存储在内存中浪费空间内。

首先介绍一种滚动数组的技术。

既然每一次计算,都只与两行状态有关,那么我们就只使用两个O(m)的数组即可,不妨记作第0行和第1行。首先把f(0,...),填入第0行;然后将算出的f(1,...)放入第1行;接下来用第1行的f(1,...)计算f(2,...),把结果再次存入第0行;之后再把f(3,...)存入第1行……

这样,只是用两个O(m)的数组,就完成了所有状态的计算,成功的将空间复杂度降至O(m)。

在本例中,如果你对使用两个O(m)的数组还感到不满意,只使用一个数组也是可以的。我们继续观察状态转移方程,之前我们利用行间的依赖关系做出了滚动数组的优化,那么我们再考虑一下行内有没有什么可以利用的性质。不难发现,f(i,j)实际上只依赖于f(i-1,k) (k=0,1...j)。从反向来考虑,也就是说f(i-1,k)只用来求f(i,j) (j=k,k+1...m)。f(i,m)算出后,f(i-1,m)就没有用了;f(i,m)和f(i,m-1)算完后,f(i-1,m-1)也没有用了……

所以我们不妨从大到小的求解每一行的状态。现在我们只有一个O(m)的数组,f(i-1,...)已经填在了里面,现在我们要计算f(i,...)。首先计算f(i,m),我们先用一个临时变量beta存储f(i,m)的值,当beta算好后,f(i-1,m)就没有用了,于是我们就可以直接把beta填入数组的第m位,也就是原来f(i-1,m)的位置。同理依次在f(i,j)算好后,直接填入数组的第j位,替换掉原先的f(i-1,j)即可。

简而言之,空间优化的原理就是尽量少地存储无用的状态。一个状态一旦失去作用(不再被其他状态依赖),就可以用新的状态将其覆盖,以此来节省空间。至于一个状态什么时候会失去作用,就需要反复观察状态转移方程,思考其中的依赖关系了。

written by PCZ

别默默的看了,快来和大家聊聊吧,登录后回答问题~ 登录 立即注册
温馨提示

非常抱歉!本站不支持旧版本IE浏览器~~建议使用IE10/IE11/Chrome/Firefox/Safari等高级浏览器浏览。

温馨提示
温馨提示
帮助与反馈

热门问题