分组背包

分组背包

分组背包其实就是通过更改和增加枚举顺序来把01背包中的状态（第i个j重量时的最大价值转化为第i组j重量时的最大价值）。

但是要注意的就是枚举顺序一定要正确

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int a[110][1010];
int w[100100], v[1010010], dp[101000];
int main()
{
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= n; i++)
	{
		int b;
		scanf("%d%d%d", &w[i], &v[i], &b);
		k = max(k, b);
		a[k][++a[k][0]] = i;
	}		
	for (int i = 1; i <= k; i++)	
		for (int c = m; c >= 0; c--)	//这个一定要在外面 ,因为如果在里面的话，1个c可能会被同一组的多个数更新，如果放在外面，一个c只会从一组里最优的结果更新过来。
			for (int j = 1; j <= a[i][0]; j++)
				if (c - w[a[i][j]] >= 0)
				dp[c] = max(dp[c], dp[c - w[a[i][j]]] + v[a[i][j]]);
	printf("%d", dp[m]);
	return 0;
}