最近在做树形dp，遇到几道多叉树的问题都可以用树上背包的做法来做。
还不是很懂，据说是分组背包，所以我就找了一道分组背包的题来打打基础
摘自《背包九讲》
这里循环顺序要注意
先枚举重量后枚举物品可以使得只取一个物品
然后最外层就是组
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
int f[MAXN], a[MAXN][MAXN];
int n, m;int main()
{while(~scanf("%d%d", &n, &m) && n){memset(f, 0, sizeof(f));REP(i, 1, n + 1)REP(j, 1, m + 1)scanf("%d", &a[i][j]);REP(i, 1, n + 1)for(int j = m; j >= 0; j--)REP(k, 1, j + 1)f[j] = max(f[j], f[j-k] + a[i][k]);printf("%d\n", f[m]);}return 0;
}