通天之分組背包（洛谷）

題目背景

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

題目描述

自 01 背包問世之後，小 A 對此深感興趣，一天，小 A 去遠遊，卻發現他的背包不同于 01 背包，

他的物品大緻可分為 k 組，每組中的物品互相沖突，現在，他想知道最大的利用價值是多少。

輸入格式

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

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

輸出格式

一個數，最大的利用價值。

輸入樣例

45 3

10 10 1

10 5 1

50 400 2

輸出樣例

10

資料範圍

1 ≤ m, n ≤ 1000

題解

分組背包（空間優化）：

#include <iostream>
using namespace std;

const int N = 1010;

int n, m, a, b, c, MAX;
int v[N][N], w[N][N], s[N], f[N];

int main()
{
	cin >> m >> n;
	
	for (int i = 1; i <= n; i ++)
	{
		cin >> a >> b >> c;
		
		s[c] ++;
		v[c][s[c]] = a;
		w[c][s[c]] = b;
		
		MAX = max(MAX, c);
	}
	
	for (int i = 1; i <= MAX; i ++)
		for (int j = m; j >= 0; j --)
			for (int k = 1; k <= s[i]; k ++)
				if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
				
	cout << f[m] << endl;
	return 0;			
}