AcWing 1019. 庆功会 [ 多重背包问题 ]

• 多重背包问题：每种物品可用s次
• 背包的总体积V: 拨款金额m
• 物品的种数N：奖品的种数n
• 每种物品的价值w：该奖品的价值
• 每种物品的体积v：该奖品的价格
  状态表示：f[i][j]：只从前i个物品中选，且总体积不超过j的所有选法集合的最大值
  状态计算：f[i][j]=max(f[i][j],f[i-1][j-k*v]+k*w)
  在能装下的情况下每种物品可以选0次，1次，2次，，，k次
  由于数据范围较小，所以不需要进行二进制，或单调队列优化
  时间复杂度 O(nms) 大约为 3*1e7
  代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=6010;
int f[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=m;j>=v;j--)
        {
            for(int k=0;k<=s&&k*v<=j;k++)
            {
                f[j]=max(f[j],f[j-k*v]+k*w);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}