解题思路

把 M 台设备分给 N 个公司，每个公司分到 j 台有对应盈利，求最大总盈利和分配方案。

思路：动态规划（分组背包）。

设 dp[i][j] = 前 i 个公司分配 j 台设备的最大盈利。

对第 i 个公司，可以分给它 k 台（0 到 j），剩下的 j-k 台给前 i-1 个公司：

dp[i][j] = max(dp[i-1][j-k] + profit[i][k])，k 从 0 到 j

怎么回溯分配方案？ 用 path[i][j] 记录 dp[i][j] 达到最优时第 i 个公司分了多少台。算完后从最后一个公司往前回溯，得到每个公司的分配数。

举例：3 公司 3 台设备

• DP 算出最大盈利 70
• 分配：每个公司 1 台

参考代码

#include <iostream>
using namespace std;

int profit[15][15];
int dp[15][15];
int path[15][15];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) cin >> profit[i][k];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int mx = 0, bestK = 0;
            for (int k = 0; k <= j; k++) {  // 第 i 公司分 k 台
                int cur = dp[i - 1][j - k] + profit[i][k];
                if (cur > mx) {
                    mx = cur;
                    bestK = k;
                }
            }
            dp[i][j] = mx;
            path[i][j] = bestK;
        }
    }

    // 回溯分配
    int assign[15];
    int rem = m;
    for (int i = n; i >= 1; i--) {
        assign[i] = path[i][rem];
        rem -= assign[i];
    }

    cout << dp[n][m] << endl;
    for (int i = 1; i <= n; i++) {
        cout << i << " " << assign[i] << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N×M²)，枚举公司和设备数
• 空间复杂度：O(N×M)，DP 数组