问题描述
玩家小豆是一位魔兽世界玩家，里面装备装备有装备等级的概念，装备等级越高的角色越厉害，现在小豆手中有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个物品可以装进背包时，有两种选择。
- 装进背包，在这个条件下，所选方案的最大利益是
。
表示当背包容量为j-w[i]时，对于可选择的前i-1个物品的最大利益。
- 不装进背包，在这个条件下，所选方案的最大利益与
相同。
通过比较这两个情况来选择更优的那一方。
有了单约束背包问题的状态方程后，就便于我们理解双约束背包问题的状态方程。
其中：
- State(i,j,k)表示，对于可选择的前i个物品，当背包容量是j，背包可容纳件数是k时，所有选择中的最大价值。
- w[i] 表示，第i个物品的重量(weight)
- v[i] 表示，第i个物品的价值(value)
对于①式：该式表明，当第i个物品的重量大于背包容量时，该物品无法装进背包。则对于可选择的前i个物品与可选择的前i-1个物品，他们的最佳利益选择方式相同，最佳利益值也相同。
对于②式：该式表明，当第i个物品可以装进背包时，有两种选择。
- 装进背包，在这个条件下，所选方案的最大利益是
。
表示当背包容量为j-w[i]且可容纳件数为k-1时，对于可选择的前i-1个物品的最大利益。
- 不装进背包，在这个条件下，所选方案的最大利益与
相同。
通过比较这两个情况来选择更优的那一方。
如果你理解到这里，那么对于更多重约束的背包问题，也已经可以写出状态转移方程了。
边界条件
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()
