P2066 機器分配 - 洛谷

題目描述

總公司擁有高效設備M臺，準備分給下屬的N個分公司。各分公司若獲得這些設備，可以為國家提供一定的盈利。問：如何分配這M臺設備才能使國家得到的盈利最大？求出最大盈利值。其中M?15，N?10。分配原則：每個公司有權獲得任意數目的設備，但總臺數不超過設備數M。

輸入格式

第一行有兩個數，第一個數是分公司數N，第二個數是設備臺數M。

接下來是一個N×M的矩陣，表明了第i個公司分配j臺設備的盈利。

最大盈利值相同時，要求編號小的公司分得設備盡可能少。

輸出格式

第一行為最大盈利值。

接下來N行為第i分公司分x臺。

輸入輸出樣例

輸入 #1	輸出 #1
3 3 30 40 50 20 30 50 20 25 30	70 1 1 2 1 3 1

思路：
代碼：

#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個公司開始DFScout << max_profit << endl;  // 輸出最大盈利for (int i = 1; i <= n; i++) {cout << i << " " << best[i] << endl;  // 輸出最優分配方案}return 0;
}