最近在做树形dp，遇到几道多叉树的问题都可以用树上背包的做法来做。

还不是很懂，据说是分组背包，所以我就找了一道分组背包的题来打打基础

摘自《背包九讲》

 

这里循环顺序要注意

先枚举重量后枚举物品可以使得只取一个物品

然后最外层就是组

#include
    
     #include
     
      #include
      
       #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;	}