背包问题

01背包问题

有 $N$ 件物品和一个容量为 $C$ 的背包。第 $i$ 件物品的大小是 $w[i]$，价值是 $v[i]$。求解将哪些物品装入背包可使价值总和最大。

$f[i][j]$ 表示前 $i$ 件物品恰放入一个容量为 $j$ 的背包可以获得的最大价值

状态转移方程：

$$f[i][j]=max\{f[i-1][j],f[i-1][j-w[i]]+v[i]\}$$

详细解释：“将前 $i$ 件物品放入容量为 $j$ 的背包中”这个子问题，若只考虑第 $i$ 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 $i-1$ 件物品的问题。如果不放第 $i$ 件物品，那么问题就转化为“前 $i-1$ 件物品放入容量为 $j$ 的背包中”，价值为 $f[i-1][j]$；如果放第 $i$ 件物品，那么问题就转化为“前 $i-1$ 件物品放入剩下的容量为 $j-w[i]$ 的背包中”，此时能获得的最大价值就是 $f[i-1][j-w[i]]$ 再加上通过放入第 $i$ 件物品获得的价值 $v[i]$。

优化后伪代码：

for i = 1 to N
    for j = C to w[i]
        f[j] = max{f[j], f[j - w[i]] + v[i]};

注意：

如果要求恰好装满背包，那么在初始化时除了 $f[0]$ 为 $0$ 其它 $f[1\dots C]$ 均设为 $-\infty$，这样就可以保证最终得到的 $f[N]$ 是一种恰好装满背包的最优解。

如果只希望价格尽量大，初始化时应该将 $f[0\dots C]$ 全部设为 $0$。

完全背包问题

有 $N$ 种物品和一个容量为 $C$ 的背包，每种物品都有无限件可用。第 $i$ 种物品的大小是 $w[i]$，价值是 $v[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

状态转移方程：

$$f[i][j]=max\{f[i-1][j-k*w[i]]+k*v[i]|0<=k*w[i]<=v\}$$

转化为01背包问题求解

状态转移方程可以等价地变形成这种形式：

$$f[i][j]=max\{f[i-1][j],f[i][j-w[i]]+v[i]\}$$

伪代码：

for i = 1 to N
    for j = w[i] to C
        f[j] = max{f[j], f[j - w[i]] + v[i]};

多重背包问题

有 $N$ 种物品和一个容量为 $C$ 的背包。第 $i$ 种物品最多有 $n[i]$ 件可用，每件大小是 $w[i]$，价值是 $v[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

对于第 $i$ 种物品有 $n[i]+1$ 种策略：取 $0$ 件，取 $1$ 件$\dots$取 $n[i]$ 件。令 $f[i][j]$ 表示前 $i$ 种物品恰放入一个容量为 $j$ 的背包的最大权值，则有状态转移方程：

$$f[i][j]=max\{f[i-1][j-k*w[i]]+k*v[i] | 0<=k<=n[i]\}$$

转化为01背包问题求解

整合

procedure ZeroOnePack(weight,value)
    for j = C..cost
        f[j] = max{f[j],f[j-weight]+value}

procedure CompletePack(weight,value)
    for j = weight..C
        f[j] = max{f[j],f[j-weight]+value}

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

for i= 1..N
    if 第i件物品是01背包
        ZeroOnePack(w[i],v[i])
    else if 第i件物品是完全背包
        CompletePack(w[i],v[i])
    else if 第i件物品是多重背包
        MultiplePack(w[i],v[i],n[i])