题解 | 购物单

# 输入n,m
n, m = map(int, input().split())
# 输入物品数据
data = []
for i in range(m):
    d = list(map(int, input().split()))
    data.append(d)
# 附件编号放入主件后面
for i in range(m):
    if data[i][2] != 0:
        k = data[i][2]  # 主件编号
        data[k - 1].append(i)
# 动态规划算法
# 结果初始化
result = []
N = int(n / 10)
for i in range(N + 1):
    result.append(0)
# 动态规划-倒序遍历
for i in range(m):
    if data[i][2] == 0:  # 判定是否为主件
        N = int(n / 10)
        L = len(data[i])
        mv = int(data[i][0] / 10)  # 主件价格/10
        mw = data[i][0] * data[i][1]  # 主件满意度
        if L == 3:  # 无附件
            while 1:
                if mv > N:
                    break
                result[N] = max(result[N], result[N - mv] + mw)
                N -= 1
        elif L == 4:  # 带一个附件
            num = data[i][3]
            mv1 = int(data[num][0] / 10)
            mw1 = data[num][0] * data[num][1]
            while 1:
                if mv > N:
                    break
                result[N] = max(result[N], result[N - mv] + mw)
                if mv + mv1 <= N:
                    result[N] = max(result[N], result[N - mv - mv1] + mw + mw1)
                N -= 1
        else:
            num = data[i][3]
            mv1 = int(data[num][0] / 10)
            mw1 = data[num][0] * data[num][1]
            num2 = data[i][4]
            mv2 = int(data[num2][0] / 10)
            mw2 = data[num2][0] * data[num2][1]
            while 1:
                if mv > N:
                    break
                result[N] = max(result[N], result[N - mv] + mw)
                if mv + mv1 <= N:
                    result[N] = max(result[N], result[N - mv - mv1] + mw + mw1)
                if mv + mv2 <= N:
                    result[N] = max(result[N], result[N - mv - mv2] + mw + mw2)
                if mv + mv1 + mv2 <= N:
                    result[N] = max(
                        result[N], result[N - mv - mv1 - mv2] + mw + mw1 + mw2
                    )
                N -= 1
print(result[-1])