多重背包问题

青旅半醒 2021-12-16 12:39 305阅读 0赞

转自：[http://www.cnitblog.com/luckydmz/archive/2008/08/06/47719.aspx][http_www.cnitblog.com_luckydmz_archive_2008_08_06_47719.aspx]（背包九讲，貌似分组背包出了点问题）

题目  
有N种物品和一个容量为V的背包。第i种物品最多有n\[i\]件可用，每件费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。  
  
基本算法  
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n\[i\]+1种策略：取0件，取1件……取 n\[i\]件。令f\[i\]\[v\]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f\[i\]\[v\]=max\{f\[i-1\]\[v-k\*c\[i\]\]+ k\*w\[i\]|0<=k<=n\[i\]\}。复杂度是O(V\*∑n\[i\])。  
  
转化为01背包问题  
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n\[i\]件01背包中的物品，则得到了物品数为∑n\[i\]的01背包问题，直接求解，复杂度仍然是O(V\*∑n\[i\])。  
  
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n\[i\]件——均能等价于取若干件代换以后的物品。另外，取超过n\[i\]件的策略必不能出现。  
  
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),n\[i\]-2^k+1，且k是满足n\[i\]-2^k+1>0的最大整数。例如，如果n\[i\]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。  
  
分成的这几件物品的系数和为n\[i\]，表明不可能取多于n\[i\]件的第i种物品。另外这种方法也能保证对于0..n\[i\]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n\[i\]两段来分别讨论得出，并不难，希望你自己思考尝试一下。  
  
这样就将第i种物品分成了O(log n\[i\])种物品，将原问题转化为了复杂度为O(V\*∑log n\[i\])的01背包问题，是很大的改进。  
  
O(VN)的算法  
多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超出了NOIP的范围，故本文不再展开讲解。我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。  
  
小结  
这里我们看到了将一个算法的复杂度由O(V\*∑n\[i\])改进到O(V\*∑log n\[i\])的过程，还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。

转载于:https://www.cnblogs.com/devil-91/archive/2012/05/16/2502710.html

[http_www.cnitblog.com_luckydmz_archive_2008_08_06_47719.aspx]: http://www.cnitblog.com/luckydmz/archive/2008/08/06/47719.aspx