DP练习 - 机器分配

题目描述

某总公司拥有高效生产设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。其中M<=100，N<=100。

输入

第一行为两个整数M，N。接下来是一个N×M的矩阵，其中矩阵的第i行的第j列的数Aij表明第i个公司分配j台机器的盈利。所有数据之间用一个空格分隔。

输出

只有一个数据，为总公司分配这M台设备所获得的最大盈利。

样例输入

3 2
1 2 3
2 3 4

样例输出

4

题意比较容易理解，枚举每种公司数量和每种机器数量的情况。

注意：每次的机器数量情况又要枚举是否在某一公司的机器增加到一定数量时产生更优的解

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int pro[105][105];
int ans[105][105];

int main()
{
    int m, n;

    while (scanf("%d%d", &m, &n) != EOF)
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                scanf("%d", &pro[i][j]);

        memset(ans, 0, sizeof(ans));
        ans[1][1] = pro[1][1];
        for (int i = 1; i <= n; ++i)
        {
            ans[i][1] = ans[i-1][1];
            for (int j = 1; j <= m; ++j)
                for (int k = 0; k <= j; ++k)
                    ans[i][j] = max(ans[i][j], ans[i-1][j-k] + pro[i][k]);
        }
        printf("%d\n", ans[n][m]);
    }
    return 0;
}