背包问题(0-1背包、完全背包、多重背包)详解

柔情只为你懂 2022-06-08 00:59 355阅读 0赞

## 背包问题 ##

一个背包总容量为V, 现在有N个物品, 第i个物品容量为weight\[i\], 价值为value\[i\], 现在往背包里面装东西, 怎样装才能使背包内物品总价值最大.主要分为3类：

1.  0-1背包, 每个物品只能取0个,或者1个.
2.  完全背包, 每个物品可以取无限次.
3.  多重背包, 每种物品都有个数限制, 第i个物品最多可以为num\[i\]个.

## 求解思路 ##

利用动态规划（dynamic programming）求最优值的方法，当前状态的最优值可以转化成上一个状态的最优值，与上一个状态转移到当前状态代价的组合求最值。f\[i\]表示当前状态的最优值，f\[i-1\]表示上一个状态的最优值，s(i-1, i)表示从状态i-1转移带状态i的代价。则： f\[i\] = max\{f\[j\], f\[j\]+s(i-1, i)\}

## 具体问题分类 ##

背包问题可以根据物品个数的限制，有多种情况0-1背包，完全背包，多重背包。

### 0-1背包问题 ###

0-1背包表示每个物品只有取和不取的状态，即只能取0个或1个。  
用子问题定义状态：即f\[i\]\[j\]表示前i间物品恰放入一个容器为j的背包可以获得的最大价值。状态转移方程为：  
f\[i\]\[j\] = max\{f\[i-1\]\[j\], f\[i-1\]\[j-weight\[i\]\]+value\[i\]\}  
python代码实现如下：

def ZeroOnePack(N, V, weight, value):
        """ 0-1 背包问题(每个物品只能取0次, 或者1次) :param N: 物品个数, 如 N=5 :param V: 背包总容量, 如V=15 :param weight: 每个物品的容量数组表示, 如weight=[5,4,7,2,6] :param value: 每个物品的价值数组表示, 如value=[12,3,10,3,6] :return: 返回最大的总价值 """
    
        # 初始化f[N+1][V+1]为0, f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
        f = [[0 for col in range(V+1)] for row in range(N+1)]
    
        for i in range(1, N+1):
            for j in range(1, V+1):
                if j<weight[i-1]:  # 总容量j小于物品i的容量时，直接不考虑物品i
                    f[i][j] = f[i-1][j]
                else:
                    # 注意由于weight、value数组下标从0开始，第i个物品的容量为weight[i-1],价值为value[i-1]
                    f[i][j] = max(f[i-1][j], f[i-1][j-weight[i-1]]+value[i-1]) # 状态方程
        return f[N][V]

上面代码中例子的f\[N+1\]\[V+1\]每一步计算如下表，其中横向表示物品编号，纵向表示背包容量：

所以代码中示例取的最大价值是选取1,3,4号物品，  
总容量=5+7+2<=15满足条件，总价值=12+10+3=25.

### 完全背包问题 ###

完全背包表示每个物品可以取无限次，只要加起来总容量不超过V就可以。  
同样可以用f\[i\]\[j\]表示前i间物品恰放入一个容器为j的背包可以获得的最大价值。则其状态转移方程为：  
f\[i\]\[j\] = max\{f\[i-1\]\[j-k\*weight\[i\]\] + k\*value\[i\]\} ,其中(0 <= k <= j/weight\[i\])  
python代码实现如下：

def CompletePack(N, V, weight, value):
        """ 完全背包问题(每个物品可以取无限次) :param N: 物品个数, 如 N=5 :param V: 背包总容量, 如V=15 :param weight: 每个物品的容量数组表示, 如weight=[5,4,7,2,6] :param value: 每个物品的价值数组表示, 如value=[12,3,10,3,6] :return: 返回最大的总价值 """
        # 初始化f[N+1][V+1]为0，f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
        f = [[0 for col in range(V + 1)] for row in range(N + 1)]
    
        for i in range(1, N+1):
            for j in range(1, V+1):
                # 注意由于weight、value数组下标从0开始，第i个物品的容量为weight[i-1],价值为value[i-1]
                # j/weight[i-1]表示容量为j时，物品i最多可以取多少次
                f[i][j] = f[i - 1][j]  # 初始取k=0为最大，下面的循环是把取了k个物品i能获得的最大价值赋值给f[i][j]
                k = 1
                while j - k * weight[i-1] >= 0:
                    f[i][j] = max(f[i][j], f[i-1][j-k*weight[i-1]]+k*value[i-1])  # 状态方程
                    k += 1
        return max_value

上面代码中例子的f\[N+1\]\[V+1\]每一步计算如下表，其中横向表示物品编号，纵向表示背包容量：

所以代码中示例取的最大价值是选取1号物品3个，  
总容量=5x3<=15满足条件，总价值=12x3=36.

### 多重背包问题 ###

多重背包是每个物品有不同的个数限制，如第i个物品个数为num\[i\]。  
同样可以用f\[i\]\[j\]表示前i间物品恰放入一个容器为j的背包可以获得的最大价值，且每个物品数量不超多num\[i\]。则其状态转移方程为：  
f\[i\]\[j\] = max\{f\[i-1\]\[j-k\*weight\[i\]\] + k\*value\[i\]\} ,其中(0 <= k <= min\{j/weight\[i\], num\[i\]\})

def MultiplePack(N, V, weight, value, num):
        """ 多重背包问题(每个物品都有次数限制) :param N: 物品个数, 如 N=5 :param V: 背包总容量, 如V=15 :param weight: 每个物品的容量数组表示, 如weight=[5,4,7,2,6] :param value: 每个物品的价值数组表示, 如value=[12,3,10,3,6] :param num: 每个物品的个数限制，如num=[2,4,1,5,3] :return: 返回最大的总价值 """
    
        # 初始化f[N+1][V+1]为0，f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
        f = [[0 for col in range(V + 1)] for row in range(N + 1)]
        for i in range(1, N+1):
            for j in range(1, V+1):
                # 对于物品i最多能取的次数是j/weight[i-1]与num[i-1]中较小者
                max_num_i = min(j/weight[i-1], num[i-1])
                # 初始取k=0为最大，下面的循环是把取了k个物品i能获得的最大价值赋值给f[i][j]
                f[i][j]= f[i - 1][j]  
                for k in range(max_num_i+1):
                    f[i][j]= max(f[i][j], f[i-1][j-k*weight[i-1]]+k*value[i-1])  # 状态方程
        return f[N][V]

上面代码中例子的f\[N+1\]\[V+1\]每一步计算如下表，其中横向表示物品编号，纵向表示背包容量：

所以代码中示例取的最大价值是选取1号物品2个，4号物品选2个，  
总容量=5x2+2x2<=15满足条件，总价值=12x2+3x2=30.