题解 | #购物单#

import copy
# 思路：多组01背包取最大
# 对于主键abc，考虑：主件ab最优/c已取，ab和c子件最优

[total, num] = list(map(int,input().split(' ')))
list_ = [ list(map(int, input().split(' '))) for i in range(num)]
list_m = [[tmp[:2]] if tmp[2] == 0 else [] for tmp in list_ ]

# for tmp in list_m:
#     print(tmp)

for i in range(num):
    if list_[i][2] != 0:
        list_m[list_[i][2]-1].append(list_[i][:2])
        # 分组提取

# for tmp in list_m:
#     print(tmp)


# print((f'list_m:{list_m}'))
list_3 = [[]]
for tmp in list_m:
    if len(tmp) == 1:
        list_3[0].append(tmp[0])
        # list_m为了append设置了一层初始列表 需要删掉
    elif len(tmp) > 1:
        list_3.append(tmp)
# 合并有子件的主件及其子件
# print("list_3")
# for tmp in list_3:
#     print(tmp)


def bag01(list0:list, w:int):
    dp = [0 for i in range(w+1)]
    for i in range(len(list0)):
        for j in range(w,0,-10):
            if list0[i][0] <= j:
                dp[j] = max(dp[j], dp[j-list0[i][0]]+list0[i][0]*list0[i][1])
        # print(f'dp:{[dp[i] for i in range(0,w+1,10)]}')
    return dp[-1]
#01背包函数

# print("list_3")
# for tmp in list_3:
#     print(tmp)

# 合并背包方案
r0 = len(list_3)
r1 = 2**(r0-1)
# 总组合数
list_4 = []
list_5 = []
for i in range(r1):
    tmp4 = copy.deepcopy(list_3[0])
    tmp5 = []
    tag = f'{bin(int(str(i),10))[2:]:0>{r0}}'
    # 转成二进制标记
    # print(tag)
    for j in range(1, r0):
        if tag[j] == '1':
            tmp4 += list_3[j][1:]
            tmp5.append(list_3[j][0])
    # print(tmp4)
    # print(tmp5)
    list_4.append(tmp4)
    list_5.append(tmp5)

    # print("list_3")
    # for tmp in list_3:
    #     print(tmp)

# print("list_3")
# for tmp in list_3:
#     print(tmp)

# print('list_4')
# for tmp in list_4:
#     print(tmp)

# print('list_5')
# for tmp in list_5:
#     print(tmp)

    




max_v = 0
for i1 in range(r1):
    tmp_list = list_4[i1]
    # print(f"tmp_list:{tmp_list}")
    # 存储不同背包方案
    r5 = len(list_5[i1])
    # print(f'list_5[i1]:{list_5[i1]}')
    rest_v = sum([tmp[0]*tmp[1] for tmp in list_5[i1]])
    # print(f'rest_v:{rest_v}')
    # 含主件背包 对v和w进行初始化 对剩余部分使用背包

    rest_w = total-sum([tmp[0] for tmp in list_5[i1]])
    # print(f'w:{w}')

    # print(tmp_list)
    value = bag01(tmp_list, rest_w)
    value+=rest_v
    # print(value)
    if max_v < value:
        max_v = value 

print(max_v)