题意

有一个可以装 $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;
}

参考与鸣谢

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

from 别人的题解

#include<bits/stdc++.h>
using namespace std;
int v,n,t;
int w[1001],a[1001][32],c[1001],f[201];
int main(){
	scanf("%d%d%d",&v,&n,&t);	
	for (int i=1;i<=n;i++){
		int p;
		scanf("%d%d%d",&w[i],&c[i],&p);
		a[p][++a[p][0]]=i;
	}
		
	for (int p=1;p<=t;p++)
		for(int j=v;j>=0;j--)
			for(int i=1;i<=a[p][0];i++){
			if(j>=w[a[p][i]]){
				int tmp=a[p][i];
				if(f[j]<f[j-w[tmp]]+c[tmp])
				f[j]=f[j-w[tmp]]+c[tmp];
			}
			}
	printf("%d",f[v]);
}

#include<bits/stdc++.h>
using namespace std;
int v, n, t;
int w[31],c[31];
int a[11][32], f[201];
int main()
{
	scanf("%d%d%d",&v,&n,&t);
	for (int i = 1;i <= n;i++)
	{
		int p;
		scanf("%d%d%d",&w[i],&c[i],&p);
		a[p][++a[p][0]] = i;
		}	
	for(int k;k <= t; k++)
		for (int j = v; j >= 0; j--)
			for (int i = 1;i <= a[k][0]; i++)
				if(j >= w[a[k][i]])
				{
					int tmp = a[k][i];
					if (f[j] < f[j - w[tmp]] + c[tmp])
						f[j] = f[j - w[tmp]] + c[tmp];
				}
	printf("%d",f[v]);
	return 0;
}