SSOJ2401分组背包
3389+
作者：crxis 发布：2017-10-25 分类：01背包
题目大意：n件物品，各有重量价值分类，每种只能选一件，背包容量是m，最大能装多大价值？
题目描述
一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，…Wn，它们的价值分别为C1，C2…，Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
输入
第1行：三个整数，V（背包容量，V<=200）,N（物品数量，N<=30）和T（最大组号，T<=10）；
第2行至N+1行：每行三个整数Wi，Ci，P，表示每个物品的重量、价值、所属组号。
输出
仅一行，一个数，表示最大总价值。
样例输入
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
样例输出
20
解题思路
关键是如何保证每一组物品只选一件？把一组物品看做是一件物品，一组一组枚举，让后保证每组选一件，从大到小进行01背包——对于每一个容量，枚举该组物品的背包，如果装进去价值更大就更新。为什么这样可以保证一组只选一件？因为在计算f[m]的时候，f[m-体积]还是之前的，这一组的还没算出来，更新f[m]的时候，只是选了对这组背包中最有利的一个背包而已。
程序实现
