题目描述

blablabla

样例

blablabla

算法1

分组背包问题模型 时间：$O(n^3)$，空间$O(n^2)$

该题属于分组背包求具体方案问题。问题的难点在于如何把问题抽象成分组背包问题。

我们可以把每个公司看作是物品组。那么，一个公司选择几台设备，可以看作是这个物品组里面的物品。也就是说，我们把一个公司选择设备的数量打包起来考虑。

例如，假设一个公司A，选择1台设备的收益是30，选择2台设备的收益是40，选择3台设备的收益是50。我们把设备的数量抽象成物品：物品组A有三件物品，第一件物品的体积是1，价值是30；第2件物品的体积是2，价值是40；第3件物品的体积是3，价值是50。

题目的约束等价于：每个公司选则一件物品，在总体积不超过M的情况下能够获得收益的最大值。
此时，我们就可以用分组背包问题的模型往里面套了。首先是状态定义。考虑到该题需要求具体方案，为了于题目给的输出样例保持一致，我们还是从后往前的考虑物品组。

状态定义：$f(i,j)$表示只考虑第$i$个及其以后的公司，在选择设备数不超过$j$的情况下，能够达到的收益最大值。

状态转移方程：
$$f(i,j) = max(f(i+1,j),f(i+1,j-k)+w_{ik}|0 ≤ k ≤ m)$$
其中$k$表示第$i$个公司选择的设备数。

由于最后我们要得到具体方案，因此空间上不能优化。当我们求解具体方案的时候，需要知道最有方案路径上每个节点是从前面哪一个节点转移过来的。考虑状态转移方程，如果$f(i,j) == f(i+1,j-k)+w_{ik})$，表示$f(i,j)$是从节点$f(i+1,j-k)$转移过来，并且$f(i,j)$在最优方案的路径上，因此要输出第$i$个公司选择的设备数$k$。

时间复杂度

状态数$O(n^2)$，状态转移复杂度$O(n)$，因此整体复杂度是$O(n^3)$。

求具体方案时，找转移节点复杂度是$O(n)$，路径共有$n$个节点，因此整体复杂度$O(n^2)$。

参考文献

算法提高课

C++ 代码

#include <iostream>

using namespace std;

const int N = 15, M = 20;
int f[N][M];
int w[N][M];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
        }
    }

    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 0; j--) {
            for (int k = 0; k <= j; k++) {
                f[i][j] = max(f[i][j], f[i+1][j-k] + w[i][k]);
            }
        }
    }

    cout << f[1][m] << endl;

    for (int i = 1, j = m; i <= n; i++) {
        for (int k = 0; k <= j; k++) {
            if (f[i][j] == f[i+1][j - k] + w[i][k]) {
                cout << i << ' ' << k << endl;;
                j = j - k;
                break;
            }
        }
    }

    return 0;
}