多重背包问题

#include<bits/stdc++.h>
using namespace std;
#define N  10001
int m,n,t;
int dp[N];
vector<pair<int,int>>v[N];

int main() 
{
    cin>>m>>n;
    int a,b,x;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>x;
        t=max(t,x);
        v[x].push_back(make_pair(a,b));
    }
    for(int i=1;i<=t;i++)
    {
        for(int k=m;k>=0;k--)
        for(int j=0;j<v[i].size();j++)   
            {
                if(k>=v[i][j].first)
                {
                    dp[k]=max(dp[k],dp[k-v[i][j].first]+v[i][j].second);
                }
            }
    }
    cout<<dp[m]<<endl;
}

背包空间由大到小，实现了dp[k-v[i][j].first]都是上一次i计算出的，即实现了每个种类只拿一个的约束。