题解 2133: 信息学奥赛一本通T1269-庆功会

解题思路:多重背包的模板题，就是在01背包的基础上多加了一个循环取奖品的个数

参考代码:

//
// Created by 15420 on 2021/5/20.
//

#include <iostream>
using namespace std;
int n,m,v[510],w[510],s[510],dp[6600];
int main()
{
    cin>>n>>m;//n代表希望购买的奖品的种数，m表示拨款金额。
    for (int i = 1; i <=n ; ++i) {
        cin>>v[i]>>w[i]>>s[i];//分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）
    }
    for (int i = 1; i <=n ; ++i) {//其实就是01背包多加了一个循环取奖品的个数
        for (int j = m; j >=1 ; --j) {
            for (int k = 0; k <=s[i]&&j>=k*v[i] ; ++k) {//购买奖品的个数不能超过s[i]个,取k个i物品价值不能超过总价值
                dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);//这里是取和不取k个奖品那个更好
            }
        }
    }
    cout<<dp[m];//最后输出奖品的最大总价值
    return 0;
}