题解 | 【模板】多重背包

def solve_multiple_knapsack_optimized(n, m, items):
    # 二进制优化后的物品列表
    binary_items = []
    
    # 将物品按二进制拆分
    for w, v, s in items:
        k = 1
        while s > 0:
            amount = min(k, s)
            binary_items.append((w * amount, v * amount))
            s -= amount
            k *= 2
    
    # 01背包问题求解
    dp = [0] * (m + 1)
    for w, v in binary_items:
        for j in range(m, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    
    return dp[m]

# 主程序
T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    items = []
    for _ in range(n):
        w, v, s = map(int, input().split())
        items.append((w, v, s))
    result = solve_multiple_knapsack_optimized(n, m, items)
    print(result)