分组背包

分组背包的明显特征就是物品间有明显的分组。

常见的模型有：

• 每组中只能选择一个物品

• 每多取一组就要产生额外花费→参考依赖背包

在具体实现时，我们通常需要对于每一组分别考虑，最后将答案组合。

例题 #1 ACboy needs your help

Problem Description 问题描述

ACbboy 这学期有 N 门课程，他计划最多花 M 天时间学习。当然，他将从不同的课程中获得的利润取决于他花在上面的日子。如何安排N门课程的M天，实现利润最大化？

Input 输入

输入由多个数据集组成。数据集从包含两个正整数 N 和 M 的行开始，N 是课程数，M 是 ACboy 的天数。接下来是矩阵 A[i][j]，（1<=i<=N<=100,1<=j<=M<=100）。A[i][j] 表示如果 ACboy 在 i 课程上花费 j 天，他将获得价值 A[i][j] 的利润。 N = 0 和 M = 0 时结束输入。

Output 输出

对于每个数据集，您的程序应输出一行，其中包含 ACboy 将获得的最大利润的数量。