python动态规划问题求解背包问题

Question

问题描述：n个金币从某些装备中购买一些装备，使攻击力达到最大化（不要省钱，每个装备只能买一件）。假设每个装备具有指定的价格和一定的攻击力，初始攻击力为0，计算出用n个金币购买设备能够获得的最大攻击力为多少。

输入：
第一行输入一个正整数r，表示可供选择装备的数量(r∈[3,100])。
接下来r行输入每个装备的参数，每行第一个数为价格value，第二个数为攻击力atk（价格和攻击力都为正整数），value和atk中间用一个空格隔开，其中value,atk∈[1,100]。这r行输入的装备拥有编号，按顺序从 0 到 r - 1。
最后一行输入游戏开局金币数值n(n为正整数，n∈[1,1000])。

输出：
输出包括一行,为用n个金币购买设备所能够获得的最大攻击力。
输入样例：
3
5 9
9 10
6 12
19
输出样例：
22

Answer 1

r = int(input())
eq = []
for i in range(r):
    v,a=map(int, input().split())
    eq.append((v,a))
n = int(input())
dp = [[0 for j in range(n+1)] for i in range(r)]
for i in range(r):
    for j in range(1, n+1):
        if i == 0:
            if j >= eq[i][0]:
                dp[i][j] = eq[i][1]
        else:
            if j >= eq[i][0]:
                dp[i][j] = max(dp[i-1][j-eq[i][0]] + eq[i][1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
print(dp[r-1][n])