信息学奥赛一本通 1266：【例9.10】机器分配

ybt 1266：【例9.10】机器分配

补充条件：如果存在几种分配方案能得到的最大盈利相同，选择前面的公司分配得少，后面的公司分配得多的方案输出。
例：如果输入数据为

3 3

输出应该为

30
1 0
2 3

而不是

30
1 3
2 0

本题与多重背包类似

集合：设备分配的方案
限制：前几家公司，分配多少设备
属性：总盈利
条件：最大
统计量：总盈利值
状态定义：dp[i][j]：对前i家公司分配j台设备能获得的最大盈利。

记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]
• 以上所有情况取最大值。

数组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]台设备；
依此类推，直到完成输出第一家公司的设备数。
此处取值的过程是倒序的，因此可以使用递归的方式倒序进行该过程，即可得到正序的输出。

#include
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;
}