多重背包

2021-08-04

多重背包问题性质

一个背包，它最大能收纳的重量为 $packWeight$。

一组物品，每种物品有一个或多个，第 $i$ 种物品的重量为 $weights[i]$，价值为 $values[i]$，数量为 $nums[i]$。

求背包能容纳的物品最大价值。这就是多重背包问题，很显然其与 $01$ 背包和完全背包的差别是：

$01$ 背包的物品列表中，每种物品仅有 $1$ 件。
完全背包的物品列表中，每种物品有无数件。
组合背包的物品列表中，每种物品有对应的指定数量的件数。

问题分析

在 $01$ 背包问题中，物品只能选择一次，在实现中使用逆序遍历背包来防止物品被重复选取。

在完全背包问题中，物品可以选择无数次，在实现中通过正序遍历背包来处理。

而在多重背包中，物品有指定的数量，以上两种处理方式都无法满足了。直观的想法是需要在处理的过程中控制选择物品的次数。

另一种方案就是将多重背包转化为 $01$ 背包，只要把物品列表里的物品按照其数量展开就可以了。

例如：

$\begin{array}{|c|c|c|c|} \hline packWeight&4\\ \hline weights&1&3&4\\ \hline values&15&20&30\\ \hline nums&3&2&1\\ \hline \end{array}$

将物品展开

$\begin{array}{|c|c|c|c|c|c|c|} \hline packWeight&4\\ \hline weights&1&1&1&3&3&4\\ \hline values&15&15&15&20&20&30\\ \hline nums&1&1&1&1&1&1\\ \hline \end{array}$

接下来问题就转化为了 $01$ 背包问题。

golang 代码实现

func MultiPack(packWeight int, weights, values, nums []int) int {
    //展开物品，将多重背包转化为01背包
    var newWeights, newValues []int
    for i := 0; i < len(weights); i++ {
        for nums[i] > 0 {
            newWeights = append(newWeights, weights[i])
            newValues = append(newValues, values[i])
            nums[i]--
        }
    }
  
    //可以对newWeights，newValues做一下异常判断

    //定义dp数组
    dp := make([]int, packWeight + 1)

    //遍历展开后的物品列表
    for i := 0; i < len(newWeights); i++ {
        //逆序遍历背包防止重复选择
        for j := packWeight; j >= newWeights[i]; j-- {
            dp[j] = max(dp[j], dp[j - newWeights[i]] + newValues[i])
        }
    }

    return dp[packWeight]
}