HDU 1712 ACboy needs your help

HDU 1712 ACboy needs your help

题意:

一共有 \(n\) 轮，给出在每一轮中，选择 \(y\) 份获得的价值。现在一共可以选择 \(m\) 份，求最终获得的最大价值是多少。

思路:

其实相当于每一轮，只能在众多物品中选择一样，其实就是一个典型的分组背包问题了。

实现:

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N], f[N];
int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        if (!n && !m)
            break;
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &a[i][j]);

        // 枚举轮数
        for (int h = 1; h <= n; h++)
        {
            // 枚举体积
            for (int j = m; j >= 0; j--)
            {
                // 枚举物品
                for (int i = 0; i <= m; i++)
                {
                    if (j >= i)
                        f[j] = max(f[j], f[j - i] + a[h][i]);
                }
            }
        }
        printf("%d\n", f[m]);
    }
    return 0;
}