P2066 机器分配

P2066 机器分配 - 洛谷

题目描述

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

输入格式

第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。

接下来是一个N×M的矩阵，表明了第i个公司分配j台设备的盈利。

最大盈利值相同时，要求编号小的公司分得设备尽可能少。

输出格式

第一行为最大盈利值。

接下来N行为第i分公司分x台。

输入输出样例

思路：
代码：

#include<bits/stdc++.h>
using namespace std;
int n, m;
int val[20][20];  // 存储每个公司分配不同设备的盈利
int best[20];     // 最优分配方案
int current[20];  // 当前分配方案
int max_profit = 0;  // 最大盈利

// DFS函数：x=当前公司编号，Nprofit=当前盈利，Nremain=剩余设备
void dfs(int x, int Nprofit, int Nremain) 
{
    if (Nremain < 0) 
	return;  // 设备不足，剪枝
    if (x > n) 
	{  // 所有公司处理完毕
        if (Nprofit > max_profit) 
		{
            max_profit = Nprofit;
            for (int i = 1; i <= n; i++) 
			{
                best[i] = current[i];
            }
        }
        return;
    }
    // 枚举当前公司分配的设备数
    for (int k = 0; k <= Nremain; k++) 
	{
        current[x] = k;  // 记录当前分配
        dfs(x + 1, Nprofit + val[x][k], Nremain - k);  // 递归处理下一个公司
    }
}

int main() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
	{
        for (int j = 1; j <= m; j++) 
		{
            cin >> val[i][j];
        }
    }
    dfs(1, 0, m);  // 从第1个公司开始DFS
    cout << max_profit << endl;  // 输出最大盈利
    for (int i = 1; i <= n; i++) 
	{
        cout << i << " " << best[i] << endl;  // 输出最优分配方案
    }
    return 0;
}