Acwing 9 分组背包问题

背包问题的模板,以后可以背下来套用噢。

但是更多的时候要像 传送门 一样有转换的过程

 

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,s[N],v[N][N],w[N][N],f[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        for(int j=1;j<=s[i];j++)
            scanf("%d%d",&v[i][j],&w[i][j]);
    }
    f[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=s[i];k++)
                if(j>=v[i][k])
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    printf("%d\n",f[m]);
    return 0;
}

 

Acwing 9 分组背包问题

上一篇:win7安装


下一篇:WPF(C#)中Bitmap与BitmapImage相互转换