Massive Algorithms: Knapsack - MultiplePack多重背包

多重背包 | 勇幸|Thinking
P03: 多重背包问题
多重背包问题定义 & 基本实现
有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])。

把第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])种物品，将原问题转化为了复杂度为<math>O(V*Σlog n[i])的01背包问题，是很大的改进。

下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

procedure MultiplePack(cost,weight,amount)
    if cost*amount>=V
        CompletePack(cost,weight)
        return
    integer k=1
    while k<amount
        ZeroOnePack(k*cost,k*weight)
        amount=amount-k
        k=k*2
    ZeroOnePack(amount*cost,amount*weight)

Example: POJ 1742 -- Coins 传说中的男人八题，是男人就A这八题。有n种面额的硬币，面额个数分别为A_i、C_i，求最多能搭配出几种不超过m的金额？
http://massivealgorithms.blogspot.com/2014/09/poj-1742-coins.html
poj.org/problem?id=1742

int main()
{
int i, cnt;
for(i=0; i<1024; i++) w[i] = 1;
while(scanf("%d%d", &N, &V) && (N || V)) {
cnt = 0;
for(i=0; i<N; i++) scanf("%d", &c[i]);
for(i=0; i<N; i++) scanf("%d", &m[i]);
for(i=0; i<V+1; i++) f[i] = -INF;
f[0] = 0;
for(i=0; i<N; i++) {
mul_pack(f, c[i], w[i], m[i]);
}
for(i=1; i<=V; i++) if(f[i]>=0) cnt++;
printf("%d\n", cnt);
}
return 0;
}
void zo_pack(int f[], int c, int w)
{
for(int i=V; i>=c; i--) {
if(f[i-c]+w>f[i]) f[i] = f[i-c]+w;
}
}
void com_pack(int f[], int c, int w)
{
for(int i=c; i<=V; i++) {
if(f[i-c]+w>f[i]) f[i] = f[i-c]+w;
}
}
void mul_pack(int f[], int c, int w, int m)
{
if(c*m>V) {
com_pack(f, c, w);
return ;
}
for(int k=1; k<m; ) {
zo_pack(f, k*c, k*w);
m = m-k;
k *= 2;
}
zo_pack(f, c*m, w*m);
}

Knapsack - MultiplePack Binary 多重背包的二进制优化

假设第 i 种物品有 ci 件，直接扩展成 0-1 背包的话把这 ci 件物品 i 当成 ci 件不同的物品（具有相同的重量 wi 和价值 vi）处理，而二进制优化考虑的是把它分成 ck 堆物品处理，其中第 k 堆物品的重量为 mk*wi，价值为 mk*vi，mk 为一个系数。要求是由这 ck 堆物品可以组合成原 ci 件物品的任意取法。比如有 7 件相同的物品 i，可分成大小为 1+2+4 的三个堆，由 1、2、4 可以组合（加）出 0~7 范围内的所有数。

具体的划分可根据件数 ci 的二进制表示来进行，ci = 2^0 + 2^1 + 2^2 + ... + 2^k + left，k 尽可能取大，但需保证 left 不小于 0。如对于 ci=7，k 取 2，left 取 0，ci=2^0+2^1+2^2；而 ci=13=2^0+2^1+2^2+6=1+2+4+6，因此 k 取 2，left 取 6。用移位操作进行.

对于多重背包的基本实现，与完全背包是基本一样的，不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。状态转移方程如下

f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=n[i] }

代码与完全背包的区别仅在内部循环上由

for(k = 1; k <= j/weight[i]; ++k)

变为

for(k = 1; k <=n[i] && k<=j/weight[i]; ++k)

X. O(VN)的算法单调队列优化
多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解

http://blog.sina.com.cn/s/blog_4646b2720100hhmq.html
将这个多重背包问题转化为完全背包问题，也就是每个物品都有无限个，但是在循环过程中用一个数组记录：某种硬币i使用的次数，如果使用次数超过c［i]，则停止循环。
http://www.cppblog.com/flyinghearts/archive/2010/09/01/125555.aspx

http://lichamnesia.com/blog/?p=568
dp[i][j]表示前i种物品，背包大小为j的最大总价值
m[i] = min(n[i], j / we[i])
dp[i][j] = max{f[i - 1][j - k * we[i]] + k * va[i]} {0 <= k <= m[i]}

http://lichamnesia.com/blog/?p=568

多重背包一般解法
朴素的三重枚举，
将物品的数量拆成0、1、2、4……等二的指数，分别计算其价值，当做单独的物品。因为用这些数可以组合出各种<=m(m为此种物品的数量)的数，也就可以用普通的01背包

分析:
dp[i][j]表示前i种物品，背包大小为j的最大总价值
m[i] = min(n[i], j / we[i])
dp[i][j] = max{f[i - 1][j - k * we[i]] + k * va[i]} {0 <= k <= m[i]}

对于第一种方法，基本只能用来对拍，几乎所有的多重背包的题目，用第一种方法都会超时。对于第二种方法，时间复杂度为Ο(n*w*log(m))(n为物品种数，w为背包大小，m为此物品数量)，是一种比较高效的方法。

Read full article from 多重背包 | 勇幸|Thinking

Knapsack - MultiplePack多重背包

Labels

Popular Posts