主要内容 #

• 机器分配
• 求解思路
• 参考代码

1. 机器分配问题描述 #

总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M.
输入描述
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；
接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。
输出描述
第一行输出最大盈利值；
接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。
输入样例

3 3           //3个分公司分3台机器
30 40 50
20 30 50
20 25 30

输出样例

70      //最大盈利值为70
1 1     //第一分公司分1台
2 1     //第二分公司分1台
3 1     //第三分公司分1台

2. 求解思路 #

1. 确定dp数组的含义
dp[i][j]：对前i家公司分配j台设备能获得的最大盈利。
2. 确定递推公式
记p[i][j]为给第i家公司分配j台设备能获得的盈利。
集合：前i家公司分配j台设备的方案。
分割集合：第i家公司分配几台设备。

• 如果不给第i家公司分配设备，那么需要给前i-1家公司分配j台设备，最大盈利为dp[i][j] = dp[i-1][j]
• 如果给第i家公司分配1台设备，那么需要给前i-1家公司分配j-1台设备，最大盈利为dp[i][j] = dp[i-1][j-1]+p[i][1]
• 如果给第i家公司分配2台设备，那么需要给前i-1家公司分配j-2台设备，最大盈利为dp[i][j] = dp[i-1][j-2]+p[i][2]
• …
• 如果给第i家公司分配j台设备，那么需要给前i-1家公司分配0台设备，最大盈利为dp[i][j] = dp[i-1][0]+p[i][j]
• 概括上述情况，k从0到j循环，给第i家公司分配k台设备，需要给前i-1家公司分配j-k太设备，最大盈利为dp[i][j] = dp[i-1][j-k]+p[i][k]。最后，对以上所有情况取最大值。

3. 记录分配情况
数组g[i][j]表示给前i家公司分配j台设备时，第i家公司分到的设备数量。
该数组的值可以在做递推的过程中求出来。
【注意】：由于本题最终要使后面的公司尽量多分配设备，所以在求最大值时，尽量大的k赋值给g[i][j]，所以如果k从小到大循环，比较时要用<=而不是<。
递推完成后，看g[n][m]的值。
如果为0，那么最后输出n 0，接着看g[n-1][m]；
如果为1，那么最后输出n 1，接着看g[n-1][m-1]；
…
如果为k，那么第n家公司分配了k台设备，输出n k，接下来需要为前n-1家公司分配m-k台设备，给第n-1家公司分配了g[n-1][m-k]台设备；
依此类推，直到完成输出第一家公司的设备数。
此处取值的过程是倒序的，因此可以使用递归的方式倒序进行该过程，即可得到正序的输出。

3.参考程序 #

#include<iostream>
using namespace std;
#define N 20
int n, m, p[N][N], g[N][N], dp[N][N];//dp[i][j]:对前i家公司分配j台设备能获得的最大盈利。
void show(int x, int k)//输出前x家公司分配k台设备的情况 
{
    if(x == 0)
        return;
    show(x-1, k-g[x][k]);
    cout << x << ' ' << g[x][k] << endl;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> p[i][j];//p[i][j]:第i公司获得j台设备能获得的盈利 
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            for(int k = 0; k <= j; ++k)//第i家公司分配k台设备 
            {
                if(dp[i][j] <= dp[i-1][j-k]+p[i][k])//本题隐藏条件有：前面的公司尽量少分配，后
                                                    //面的公司尽量多分配。所以要选择尽量大的k赋值给g[i][k] 
                {
                    dp[i][j] = dp[i-1][j-k]+p[i][k];
                    g[i][j] = k;//g[i][j]:给前i家公司分配j台设备时，第i家公司分到的设备数量
                }
            }
    cout << dp[n][m] << endl;
    show(n, m); 
    return 0;
}