购物单

N, m = map(int, input().split(' '))  # 输入了N 和 m
N = N // 10
# 限定第一行输入的钱数和件数
if N < 3200 and m < 60:
    p1 = {}
    attach=[]
    for item in range(m):
        # 存储m个vpq,价格、重要程度和附件属性
        price, weight, indx = map(int, input().split(' '))
        price = price // 10
        # 这是主件吗？是的话
        if not indx:
            # 买，创造一个key为主件位置的键值对
            p1[item + 1] = [[price, price * weight]]
        else:
            # 为防止附件在主件之前，先将附件数据存储下来。
            attach.append([price, price * weight, indx])
    for j in range(len(attach)):
        if attach[j][2] != 0:    # 如果是附件，attach[j][2]表示所属主件
            l = len(p1[attach[j][2]])
            new = [[attach[j][0] + p1[attach[j][2]][i][0], attach[j][1] + p1[attach[j][2]][i][1]] for i in range(l)]
            p1[attach[j][2]].extend(new)
    # 这样，p1里每个键值对存储了key主件下，只买主件、主件+附件1、主件+附件2、主件+附件1+附件2 这几种情况，[价格，权重]。
    # 现在我不遍历所有情况，而是以价格为索引，权重为value创造一个列表，
    vls = [0] * (N + 1)
    for item in p1:
        for ky in range(N, 0, -1):
            for price, weight in p1[item]:
                if N >= ky >= price:
                    vls[ky] = max(vls[ky - price] + weight, vls[ky])
    print(10 * max(vls))

money, things = map(int, input().split())
money = money // 10  # money都是10的整数，整除后，减小循环次数
# 三列分别表示主件，附件1，附件2
weight = [[0] * 3 for _ in range(0, things + 1)]  # 价格
value = [[0] * 3 for _ in range(0, things + 1)]  # 价值=价格*重要度
result = [[0] * (money + 1) for _ in range(0, things + 1)]
for i in range(1, things + 1):
    prices, degree, depend = map(int, input().split())  # 分别为价格，重要性，主附件
    prices = prices // 10

    if depend == 0:  # 主件
        weight[i][0] = prices
        value[i][0] = prices * degree

    elif weight[depend][1] == 0:  # 附件
        weight[depend][1] = prices  # 第一个附件
        value[depend][1] = prices * degree

    else:
        weight[depend][2] = prices  # 第二个附件
        value[depend][2] = prices * degree
# 遍历计算
for i in range(1, things + 1):  # 每几件物品
    for j in range(money, -1, -1):
        if j >= weight[i][0]:  # 当前价格j可以容下第i个主件时,比较（上一个物品对应价格的价值）与（第i个物品的价值 + 余额价格对应上个物品价值）
            result[i][j] = max(result[i - 1][j], result[i - 1][j - weight[i][0]] + value[i][0])
            # 在确定主件可容纳，并做相应计算之后,判断附件的容纳情况，如果主件都没有办法容纳，则附件必定不可容纳
            if j >= (weight[i][0] + weight[i][1]):
                # 当可以容下第i个主件和此主件的第1个附件时，此时需要在比大小时加入当前最优，保证添加附件的结果不会反而更小
                # 比较（当前价格对应上一物品的价值）与（主键价值+附件1价值+上一物品在价格（j-主键价格-附件1价格）时对应的价值）
                result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1]] + value[i][0] + value[i][1])

            if j >= (weight[i][0] + weight[i][2]):
                # 可以容下第i个主件和此主件的第2个附件，此时也需要在比大小时加入当前最优，保证添加附件的结果不会反而更小
                # 比较（当前价格对应上一物品的价值）与（主键价值+附件2价值+上一物品在价格（j-主键价格-附件2价格）时对应的价值）,
                result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][2]] + value[i][0] + value[i][2])
                # 根据3件物品价格之和必然大于等于2件物品的规则，只有在能容纳主件和附件2时，才有判断全部容纳可能性的必要
                if j >= (weight[i][0] + weight[i][1] + weight[i][2]):
                    # 当判断通过，则判断当前值与上物品计算当前价格价值与当前3物品情况价值中最大值，同时还要比较目前最优值
                    result[i][j] = max(result[i][j], result[i - 1][j], result[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + value[i][0] + value[i][1] + value[i][2])
        else:
            # 当前价格j不能容下第i个主件时,价值为上一个物品的对应价格的价值
            result[i][j] = result[i - 1][j]
print(result[things][money] * 10)

N,m = map(int,input().split()) #N =money m=item number
N/=10
N=int(N)
values = [[0,0,0] for _ in range(m+1)]
weights = [[0,0,0] for _ in range(m+1)]
f = [[0]*(N+1) for _ in range(m+1)]
for i in range(1,m+1):
    v,p,q = map(int,input().split())
    v/=10
    v= int(v)
    if q == 0: # main 
        values[i][0] = ***bsp;       weights[i][0] = v

    else:
        if weights[q][1] == 0:
            values[q][1] = ***bsp;           weights[q][1] = v
        else:
            values[q][2] = ***bsp;           weights[q][2] = v

for i in range(1,m+1):
    for j in range(N,0,-1):
        temp = [f[i-1][j]]
        if j>=weights[i][0]: # main
            temp.append(max(f[i-1][j] , f[i-1][j-weights[i][0]] + values[i][0]))
        if j>=weights[i][0] +weights[i][1]: # main + annex 1
            temp.append(max(f[i-1][j],  f[i-1][j-weights[i][0]-weights[i][1]] + values[i][0] +  values[i][1]))
        if j>=weights[i][0] +weights[i][1] + weights[i][2]: # main + annex 1 + annex 2
            temp.append(max(f[i-1][j],  f[i-1][j-weights[i][0]-weights[i][1]-weights[i][2]]+values[i][0]+values[i][1]+values[i][2]))
        if j>=weights[i][0] + weights[i][2]: # main + annex 2
            temp.append(max(f[i-1][j],  f[i-1][j-weights[i][0]-weights[i][2]] + values[i][0] +  values[i][2]))
        f[i][j] = max(temp)
print(f[m][N]*10)
        

import sys


txt=input()
money=int(txt[0:txt.find(' ')])
n=int(txt[txt.find(' ')+1:])
v=[]
p=[]
q=[]
fushu=[]
for i in range(n):
    txt=input()
    p1=txt.find(' ')
    p2=txt.find(' ',p1+1)
    v.append(int(txt[0:p1]))
    p.append(int(txt[p1+1:p2]))
    q.append(int(txt[p2+1:])-1)
    fushu.append([])
    if q[i]>=0:
        fushu[q[i]]=fushu[q[i]]+[i]
F=[[0 for i in range(money+1)] for i in range(n)]
for i in range(0,n):
    for j in range(1,money+1):
        if q[i]<0:
            if i==0:
                F[i][j]=F[i][j-1]
            else:
                F[i][j]=max(F[i-1][j],F[i][j-1])
            if j>=v[i]:
                F[i][j]=max(F[i][j],F[i-1][j-v[i]]+v[i]*p[i])
            if len(fushu[i])==1:
                fs=fushu[i][0]
                if j>=v[i]+v[fs]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]]+v[i]*p[i],F[i-1][j-v[i]-v[fs]]+v[i]*p[i]+v[fs]*p[fs])
            if len(fushu[i])==2:
                fs1=fushu[i][0]
                fs2=fushu[i][1]
                if j>=v[i]+v[fs1]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]-v[fs1]]+v[i]*p[i]+v[fs1]*p[fs1])
                if j>=v[i]+v[fs2]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]-v[fs2]]+v[i]*p[i]+v[fs2]*p[fs2])
                if j>=v[i]+v[fs1]+v[fs2]:
                    F[i][j]=max(F[i][j],F[i-1][j-v[i]-v[fs1]-v[fs2]]+v[i]*p[i]+v[fs1]*p[fs1]+v[fs2]*p[fs2])
        else:
            F[i][j]=F[i-1][j]
print(F[n-1][money])

while True:
    try:
        total, N = map(int, input().split())
        total = total // 10
        items = {}
        for i in range(N):
            price, weight, indx = map(int, input().split())
            price = price // 10
            if indx == 0:
                items[i+1] = [[price,weight*price]]
            else:
                new = [[item[0] + price, item[1] + price * weight] for item in items[indx]]
                items[indx].extend(new)
        dp = [0] * (total + 1)
        for key in items:
            for j in range(total, 0,-1):
                for price, weight in items[key]:
                    if price <= j <= total:
                        dp[j] = max(weight + dp[j - price], dp[j])
        print(10 * max(dp))
    except:
        break

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

{1: [[80, 160], [120, 360], [110, 310], [150, 510]],
 4: [[40, 120]],
 5: [[50, 100]]}

# -*- coding: utf-8 -*-

from itertools import combinations


# 迭代附件
def iter_items(items):
    for i in range(len(items) + 1):
        yield from combinations(items, i)


# 输入多个数字
def input_ints():
    return map(int, input().split())


def main():
    # 物品字典
    items = {}
    # 公约数，用于减少数组长度，题目给了为10
    common_divisor = 10
    capacity, count = input_ints()
    capacity = int(capacity / common_divisor)
    
    for i in range(1, count + 1):
        price, weight, sub_index = input_ints()
        price = int(price / common_divisor)
        weight *= price  # 直接计算价值
        
        if sub_index == 0:
            items[i] = {
                'main': (price, weight),
                'sub': []
            }
        else:
            items[sub_index]['sub'].append((price, weight))

    max_values = [0] * (capacity + 1)
    new_max_values = []

    for item in items.values():
        for i in range(capacity + 1):
            max_value = max_values[i]

            for sub_items in iter_items(item['sub']):
                price, weight = item['main']

                for sub_price, sub_weight in sub_items:
                    price += sub_price
                    weight += sub_weight

                if price > i:
                    continue

                value = max_values[i - price] + weight
                max_value = max(max_value, value)

            new_max_values.append(max_value)

        max_values = new_max_values
        new_max_values = []

    print(max_values[-1] * common_divisor)


if __name__ == '__main__':
    main()

while True:
    try:
        total_money,total_num=map(int,input().split(' '))
        total_money//=10
        product_item=[]
        for i in range(total_num):
            v,p,q=map(int,input().split(' '))
            v//=10
            product_item+=[[i+1,v,p,q]]
        dp=[[0,[0]] for i in range(total_money+1)]
 
        for current_no,v,p,q in product_item:
            for i in range(len(dp)-1,-1,-1):
                if (i-v)>=0:
                    if not current_no in dp[i-v][1]:
                        if q in dp[i-v][1]: # the parent has been chosen.
                            if (dp[i-v][0]+v*p)>dp[i][0]:
                                dp[i][0]=dp[i-v][0]+v*p
                                dp[i][1]=dp[i-v][1].copy()
                                dp[i][1]+=[current_no]
                        else: # the parent has not been chosen, then we can pick up both current one and the parent.
                            if (i-v-product_item[q-1][1])>0:
                                if (dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2])>dp[i][0] and not current_no in dp[i-v-product_item[q-1][1]][1] and not q in dp[i-v-product_item[q-1][1]][1]:
                                    dp[i][0]=dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2]
                                    dp[i][1]=dp[i-v-product_item[q-1][1]][1].copy()
                                    dp[i][1]+=[current_no]
                                    dp[i][1]+=[q]
        print(dp[total_money][0]*10)
    except:
        break

while True:
    try:
        N, m = map(int, input().split())
        N //= 10
        ls = []
        for i in range(m):
            ls.append(list(map(int, input().split()))+[i+1])
        for i in range(len(ls)):
            ls[i][0] //= 10
        dic = {}
        for item in ls:
            if item[2] == 0:
                dic[item[3]] = [item[:2]]
        for item in ls:
            if item[2]:
                dic[item[2]].append(item[:2])
        items = []
        for item in dic.values():
            cur = []# [钱，权重]组成的列表
            cur.append([item[0][0], item[0][0]*item[0][1]])
            if len(item) > 1:
                cur.append([item[1][0]+item[0][0], item[0][0]*item[0][1]+item[1][0]*item[1][1]])
            if len(item) > 2:
                cur.append([item[2][0]+item[0][0], item[0][0]*item[0][1]+item[2][0]*item[2][1]])
                cur.append([item[2][0]+item[1][0]+item[0][0], item[0][0]*item[0][1]+item[1][0]*item[1][1]+item[2][0]*item[2][1]])
            cur.sort(key=lambda x: x[0])
            items.append(cur)
        dp = [[0]*(N+1) for i in range(len(items))]
        for i in range(len(items)):
            for j in range(N+1):
                for item in items[i]:
                    if item[0] > j:
                        dp[i][j] = max(dp[i][j], dp[i-1][j] if i>0 else 0, dp[i][j-1] if j>0 else 0)
                    else:
                        dp[i][j] = max(item[1]+(dp[i-1][j-item[0]] if i>0 else 0), dp[i][j], dp[i-1][j] if i>0 else 0, dp[i][j-1] if j>0 else 0)
        print(max(dp[-1])*10)
    except:
        break

while True:
    try:
        N,m = map(int,raw_input().split())
        f = [0]*(N+1)
        goods = []
        groups = []
        for i in range(m):
            goods.append(map(int,raw_input().split()))
        for i in range(m):
            if goods[i][2] == 0:
                group = []
                group.append(goods[i])
                for j in range(m):
                    if goods[j][2] == i + 1:
                        group.append(goods[j])
                groups.append(group)
        for i in range(len(groups)):
            group = groups[i]
            for j in range(N, group[0][0] - 1,-1):
                for k in range(0, len(group)):
                    if k == 0:
                        f[j] = max(f[j], f[j - group[0][0]] + group[0][0]*group[0][1])
                    else:
                        if j >= group[0][0] + group[k][0]:
                            f[j] = max(f[j], f[j - group[0][0] - group[k][0]] + group[0][0]*group[0][1] + group[k][0] * group[k][1])
                    if k == 2:
                        if j >= group[0][0] + group[1][0] + group[2][0]:
                            f[j] = max(f[j], f[j - group[0][0] - group[1][0] -  group[2][0]] + group[0][0]*group[0][1] + group[1][0] * group[1][1] + group[2][0] * group[2][1])
        print int(f[N])
    except:
        break