以前，有个神秘的院子里面有三种苹果，每个苹果的数量是无限的。有一个小姑娘带了一个大袋子来到院子，她从来没见过这么多的苹果。每种苹果都有大小以及出售的价格，小姑娘想获得最大的利润，但是她不知道怎么才能做到。于是她来向你寻求帮助，你能告诉她能获得的最大价值吗？ Input 第一行一个整数T(T <= 50)，表示测试数据的组数。 每组测试数据有四行组成，前三行每行有两个整数S和P，分别表示每种苹果的大小(1 <= S <= 100)和价格(1 <= P <= 10000) 第四行有一个整数V(1 <= V <= 100,000,000)表示小姑娘袋子的大小。 Output 每组测试数据输出组数和小姑娘能得到的最大的价值。 Sample Input 1 1 1 2 1 3 1 6 Sample Output Case 1: 6

这是一道经典的背包问题，可以使用动态规划来解决。我们可以定义一个二维数组 dp[i][j] 表示在前 i 种苹果中，背包容量为 j 时能获得的最大价值。对于每个物品，它可以选择放入或不放入背包中，因此有以下状态转移方程：

- 如果不放第 i 个苹果，那么 dp[i][j] = dp[i-1][j]；
- 如果放第 i 个苹果，那么 dp[i][j] = dp[i][j-Si] + Pi；

最终的答案就是 dp[3][V]，其中 V 是背包的容量。注意，因为每种苹果数量是无限的，所以第二个状态转移方程中的 dp[i] 应该是 dp[i][j-Si]，而不是 dp[i-1][j-Si]。

下面是 AC 代码：