01背包问题：双重约束

问题描述

玩家小豆是一位魔兽世界玩家，里面装备装备有装备等级的概念，装备等级越高的角色越厉害，现在小豆手中有n个金币，但身上最多穿着m件装备，每件装备的对应的价格x金币，对应的装备等级是y。现在小豆想要用手中的金币买到装备等级最大的装备组合。问小豆能买到最大的装备等级。

输入描述

金币数量n
最多穿装备的数量m
价格x，装备等级y

输出描述

能买到的装备等级加和

样例输入

130
3
100 380
20 320
40 360
50 310

样例输出

990

---

解题思路

很显然，这道题就是典型的背包问题，只不过它有两个约束条件，一个是手中金币数量n，即背包容量，另一个是最多穿着m件，即数量约束。

状态转移方程

首先我们先给出单约束背包问题的状态转移方程

其中 ：

• State(i,j)表示，对于可选择的前i个物品，当背包容量是j时，所有选择中的最大价值。
• w[i] 表示，第i个物品的重量(weight)
• v[i] 表示，第i个物品的价值(value)

对于①式：该式表明，当第i个物品的重量大于背包容量时，该物品无法装进背包。则对于可选择的前i个物品与可选择的前i-1个物品，他们的最佳利益选择方式相同，最佳利益值也相同。

对于②式：该式表明，当第i个物品可以装进背包时，有两种选择。

1. 装进背包，在这个条件下，所选方案的最大利益是 。 表示当背包容量为j-w[i]时，对于可选择的前i-1个物品的最大利益。
2. 不装进背包，在这个条件下，所选方案的最大利益与 相同。

通过比较这两个情况来选择更优的那一方。

---

有了单约束背包问题的状态方程后，就便于我们理解双约束背包问题的状态方程。

其中：

• State(i,j,k)表示，对于可选择的前i个物品，当背包容量是j，背包可容纳件数是k时，所有选择中的最大价值。
• w[i] 表示，第i个物品的重量(weight)
• v[i] 表示，第i个物品的价值(value)

对于①式：该式表明，当第i个物品的重量大于背包容量时，该物品无法装进背包。则对于可选择的前i个物品与可选择的前i-1个物品，他们的最佳利益选择方式相同，最佳利益值也相同。

对于②式：该式表明，当第i个物品可以装进背包时，有两种选择。

1. 装进背包，在这个条件下，所选方案的最大利益是 。 表示当背包容量为j-w[i]且可容纳件数为k-1时，对于可选择的前i-1个物品的最大利益。
2. 不装进背包，在这个条件下，所选方案的最大利益与 相同。

通过比较这两个情况来选择更优的那一方。

如果你理解到这里，那么对于更多重约束的背包问题，也已经可以写出状态转移方程了。

边界条件

python实现

def get_input():
    n = 130
    m = 3
    eq_list = [(100, 380), (20, 320), (40, 360), (50, 310)]
    return n, m, eq_list

def main():
    # get the input
    n, m, eq_list = get_input()
    # define the state matrix, for fast performance. And the boundary conditions are initialized.
    # state[len(eq_list) + 1][n + 1][m + 1]
    state = [[[0 for _ in range(m + 1)] for _ in range(n + 1)] for _ in range(len(eq_list) + 1)]

    for k in range(1, m + 1):
        for j in range(1, n + 1):
            for i in range(1, len(eq_list) + 1):
                # in here the ith item in eq_list is eq_list[i-1] because i is in [1,len(eq_list)+1]
                # the value which means the level of equipments here
                v = eq_list[i - 1][1]
                # the weight which means the price of equipments here
                w = eq_list[i - 1][0]
                if w > j: # the item cant be put in bag
                    state[i][j][k] = state[i-1][j][k]
                else:
                    state[i][j][k] = max(state[i-1][j][k], # the case that do not put the item into bag
                                         state[i-1][j-w][k-1] + v) # the case that put the item into bag

    # the maximum value of bag problem
    print(state[len(eq_list)][n][m])

if __name__ == '__main__':
    main()