分组背包 python

解题思路:

动态规划，01背包衍生题型，只需多一个循环来遍历决策即可。

注意事项:

注意背包体积要大于物品体积才能将物品放入

参考代码:

c, n, t = map(int, input().split())

dp = [0] * (c+1)

nums = []

for _ in range(n):

    nums.append(list(map(int, input().split())))

for j in range(1, t+1):

    num = []

    for k in range(n):

        if nums[k][2] == j:

            num.append(nums[k])

    for i in range(c, 0, -1):

        for v, w, s in num:

            if i >= v:

                dp[i] = max(dp[i], dp[i-v]+w)

print(dp[c])