洛谷 P1757 通天之分組背包

題目背景

直達通天路·小A曆險記第二篇

題目描述

自01背包問世之後，小A對此深感興趣。一天，小A去遠遊，卻發現他的背包不同于01背包，他的物品大緻可分為k組，每組中的物品互相沖突，現在，他想知道最大的利用價值是多少。

輸入格式

兩個數m,n，表示一共有n件物品，總重量為m

接下來n行，每行3個數ai,bi,ci，表示物品的重量，利用價值，所屬組數

輸出格式

一個數，最大的利用價值

輸入輸出樣例

輸入 #1複制

45 3

10 10 1

10 5 1

50 400 2

輸出 #1複制

10

說明/提示

1<=m<=1000 1<=n<=1000 組數t<=100

分組背包闆子

#include<cstdio>
#include<algorithm>
#define re register int
using namespace std;
int n,m,x,cm,a[1010],b[1010];
int c[1010][1010],f[1010];
int main() {
	scanf("%d%d",&n,&m);
	for(re i=1;i<=m;i++) {
		scanf("%d%d%d",&a[i],&b[i],&x);
		cm=cm>x?cm:x; c[x][++c[x][0]]=i;
	}
	for(re i=1;i<=cm;i++) {
		for(re j=n;j>=0;j--) {
			for(re k=1;k<=c[i][0];k++) {
				if(j>=a[c[i][k]]) {
					f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);
				}
			}
		}
	}
	printf("%d",f[n]);
	return 0;
}