【正经题解】多重背包-买奖品

这段代码使用动态规划求解多重背包问题，其中 $dp$ [ $j$ ] 表示拨款金额为 $j$ 时的最大价值。通过三重循环遍历每种奖品、拨款金额和购买数量，更新最大价值。最终输出最大价值。

#include <iostream>
using namespace std;

// 定义商品价格、价值和最大数量的数组
int w[10005], c[10005], n[10005];

// 定义动态规划数组
int dp[10005];

int main() {
    // 输入购买的奖品总数和拨款金额
    int N, M;
    cin >> N >> M;

    // 输入每种奖品的价格、价值和最大数量
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i] >> n[i];
    }

    // 遍历每种奖品
    for (int i = 1; i <= N; i++) {
        // 遍历拨款金额
        for (int j = M; j >= 0; j--) {
            // 遍历购买数量
            for (int k = 1; k <= n[i]; k++) {
                // 判断是否能够购买
                if (j >= w[i] * k) {
                    // 更新最大价值
                    dp[j] = max(dp[j], dp[j - w[i] * k] + c[i] * k);
                }
            }
        }
    }

    // 输出最大价值
    cout << dp[M] << endl;

    return 0;
}