【模板】分组背包

记住体积倒序,因为每组只能取一个

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
int dp[110], v[110], w[110];
int n, m, s;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s;
        for(int j = 1; j <= s; j++)
            cin >> v[j] >> w[j];
        for(int j = m; j >= 0; j--)
            for(int k = 1; k <= s; k++)
                if(j >= v[k])
                    dp[j] = max(dp[j], dp[j-v[k]]+w[k]);
                     
    }
    cout << dp[m];
    return 0;
}

 

上一篇:CCNP路由综合实验(201912月新版)


下一篇:从KVM上给虚机挂网卡