题解 | #资产包打包#
资产包打包
https://www.nowcoder.com/practice/a47c1795e32c43d38701af7862a4b359
# format input
arr = list(input().split(','))
M = int(arr[0])
n = int(arr[1])
weight = list(map(int, arr[2].split()))
value = list(map(int, arr[3].split()))
# base case
dp = [[0] * (M + 1) for _ in range(n + 1)]
# 定义 dp[i][j] 代表前i个物品 数量为j 可得的最大价值
# 遍历状态
for i in range(1, n + 1):
for j in range(1, M + 1):
if j - weight[i - 1] < 0:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j ], \
value[i - 1] + dp[i - 1][j - weight[i - 1]])
print(dp[n][M])
用二维dp数组定义如下状态：
dp [i][j]
从前 i 个资产中选择，且条数不超过 j 时可获得的最大价值
base case ： i = 0 or j =0->dp = 0
因为当可选的资产数为0 或者条数限制为0时，可获得的价值也为0
循环填充 dp table:
【Example】：
输入：10,10,4 9 10 3 4 10 8 9 5 10,7902 5742 5587 9719 5251 8964 6582 4498 2023
即有10 个资产
| weight |
4 |
9 | 10 | 3 | 4 | 10 | 8 | 9 | 5 | 10 |
| value |
7902 |
5742 |
5587 |
9719 |
5251 |
8964 |
6582 |
4498 |
7669 |
2023 |
循环的过程其实是枚举dp状态，对于每个状态：
如果包里还可以容纳第i个物品：
更新dp = 选择最大（不添加第i个物品的价值， 添加第i个物品的价值）
否则：
更新dp = 不添加第i个物品的价值 # 因为放不下
查看11道真题和解析
