题意

有一个可以装 $m$ kg 的背包，$n$ 个物品，被分为 $t$ 组。

每个物品有一个重量 $w$，一个价值 $v$，以及它所在的组别 $p$

每组只能拿一个物品，让拿的价值最大

思路

一组一组遍历，让每组拿到最大的价值后再遍历下一组

这里把第 $i$ 个重量的最大价值算完后再到下一个重量

代码

#include <bits/stdc++.h>
using namespace std;
int a[205],f[15][35],w[35],v[35];
int main(int argc, char **argv){
	int m,n,t;
	cin >> m >> n >> t;
	for (int i = 1;i <= n;i++){
		int p;
		cin >> w[i] >> v[i] >> p;
		f[p][++f[p][0]] = i;	// f[p][0] 是存第 p 组有多少个物品
	}
	for(int p = 1;p <= t;p++){	// 遍历组（拿出每组的最大价值）
		// 循环内外不能错！！
		for (int i = m;i > 0;i--){	// 遍历重量
			for (int j = 1;j <= f[p][0];j++){	// 遍历本组的物品
				if (i >= w[f[p][j]])	// 最大重量要够才能装下
				a[i] = max(a[i - w[f[p][j]]] + v[f[p][j]],a[i]);
			}
		}
	}
	cout << a[m];
	return 0;
}

参考与鸣谢

本题解参考了的题解：点我查看