目录
显示
题目
题解
思路是好的，提出从附件为0、1、2个四种情况讨论（是四种不是三种因为附件为2个的情况可以选第一个，也可以选第二个），主件一定选的情况下，附件有这四种可能：
- 00： 代表附件都不选
- 01： 代表选择第二个附件
- 10： 代表选择第一个附件
- 11： 代表两个附件都选
代码
- 首先读取输入：
n, m = map(int, input().split())- 然后定义
prices和values分别存储主件以及其附件的价格和价值，
from collections import defaultdict
prices = defaultdict(lambda: [0, 0, 0]) # 主从物品的价格
values = defaultdict(lambda: [0, 0, 0]) # 主从物品的价值
for i in range(m): # i 代表第 i + 1 个物品
v, p, q = map(int, input().split())
v //= 10 # 价格总为 10 的倍数，优化空间复杂度
if q == 0: # 追加主物品
prices[i + 1][0] = v
values[i + 1][0] = v * p
elif prices[q][1]: # 追加从物品
prices[q][2] = v
values[q][2] = v * p
else:
prices[q][1] = v
values[q][1] = v * p假如输入为：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0这里的prices和values分别如下：
prices: {1: [80, 40, 30], 4: [40, 0, 0], 5: [50, 0, 0]}
values: {1: [160, 200, 150], 4: [120, 0, 0], 5: [100, 0, 0]}因为索引为2和3的都是附件，所以这里没有key为2和3，而是加入到了他们对应的主件，即，key=1的里面。
- 然后定义动态数组
dp = [0] * (n + 1) # 初始化 dp 数组- 处理四种情况
for i, v in prices.items():
for j in range(n, v[0] - 1, -1):
p1, p2, p3 = v
v1, v2, v3 = values[i]
# 处理主从组合的四种情况
dp[j] = max(dp[j], dp[j - p1] + v1)
dp[j] = max(dp[j], dp[j - p1 - p2] + v1 + v2) if j >= p1 + p2 else dp[j]
dp[j] = max(dp[j], dp[j - p1 - p3] + v1 + v3) if j >= p1 + p3 else dp[j]
dp[j] = (
max(dp[j], dp[j - p1 - p2 - p3] + v1 + v2 + v3)
if j >= p1 + p2 + p3
else dp[j]
)
print(dp[n] * 10)- 完整代码
from collections import defaultdict
# 处理输入
n, m = map(int, input().split())
n //= 10 # 价格总为 10 的倍数，优化空间复杂度
prices = defaultdict(lambda: [0, 0, 0]) # 主从物品的价格
values = defaultdict(lambda: [0, 0, 0]) # 主从物品的价值
for i in range(m): # i 代表第 i + 1 个物品
v, p, q = map(int, input().split())
v //= 10 # 价格总为 10 的倍数，优化空间复杂度
if q == 0: # 追加主物品
prices[i + 1][0] = v
values[i + 1][0] = v * p
elif prices[q][1]: # 追加从物品
prices[q][2] = v
values[q][2] = v * p
else:
prices[q][1] = v
values[q][1] = v * p
# 处理输出
dp = [0] * (n + 1) # 初始化 dp 数组
for i, v in prices.items():
for j in range(n, v[0] - 1, -1):
p1, p2, p3 = v
v1, v2, v3 = values[i]
# 处理主从组合的四种情况
dp[j] = max(dp[j], dp[j - p1] + v1)
dp[j] = max(dp[j], dp[j - p1 - p2] + v1 + v2) if j >= p1 + p2 else dp[j]
dp[j] = max(dp[j], dp[j - p1 - p3] + v1 + v3) if j >= p1 + p3 else dp[j]
dp[j] = (
max(dp[j], dp[j - p1 - p2 - p3] + v1 + v2 + v3)
if j >= p1 + p2 + p3
else dp[j]
)
print(dp[n] * 10)
