제출 #746235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
746235		iamjiamingliu	Knapsack (NOI18_knapsack)	Cpython 3	0 / 100	1086 ms	10668 KiB

knapsack

max_capacity, items_cnt = map(int, input().split())
dp = [[0] * (max_capacity + 1) for _ in range(items_cnt + 1)]

for item_i in range(items_cnt):
    value, weight, quantity = map(int, input().split())
    for cur_capacity in range(max_capacity + 1):
        dp[item_i + 1][cur_capacity] = dp[item_i][cur_capacity]
        for cur_quantity in range(1, quantity + 1):
            if cur_quantity * weight > cur_capacity:
                dp[item_i + 1][cur_capacity:] = [dp[item_i + 1][cur_capacity - 1]] * (max_capacity - cur_capacity + 1)
                break
            dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - cur_quantity * weight] + cur_quantity * value)

print(dp[-1][-1])
# print(*dp, sep='\n')

"""
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
"""

"""
20 3
5000 15 1
100 1 3
50 1 4
"""

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27