分组背包

大玉们写的不懂，自己再写一篇

转移方程

f[i][j]表示前i组容量为j时的最大价值
f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k]]+w[i][k]);1<k<K

#include<map>
#include<cstdio>

using namespace std;

const int N=1010;

map<int,int>id;
int n,m,num;
int g[N][N],t[N];
int v[N],w[N],f[N][N];

int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v[i],&w[i],&t[i]);
        id[t[i]]++;
        num=max(num,t[i]);
        g[t[i]][id[t[i]]]=i;
    }
    for(int i=1;i<=num;i++)
        for(int j=m;j>=0;j--){
            f[i][j]=f[i-1][j];
            for(int k=1;k<=id[i];k++)
                if(j>=v[g[i][k]])
                f[i][j]=max(f[i][j],f[i-1][j-v[g[i][k]]]+w[g[i][k]]);
        }
    printf("%d\n",f[num][m]);
    return 0;
}

如何实现分组？由状态转移方程
可得每次转移都与上一个分组有关，故我们可以优化：

下次补