$\color{red}{DP}$——目录

题目大意：

总公司拥有 $M$ 台 相同 的高效设备，准备分给下属的 $N$ 个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出在最大盈利值的情况下的方案

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

解题方法：

每个分公司中，选择给的物品数，只有一种方案，就使我们突发奇想，想到了 分组背包问题。
重点就是方案怎么求。
我们先上代码再说，在代码里面来理解

int j = m;
for (int i = n; i; i -- ) {
    for (int k = 0; k <= j; k ++ ) {
        if (f[i][j] == f[i - 1][j - k] + w[i][k]) { //如果选择了物品
            way[i] = k;
            j -= k;
            break;//记录答案，然后直接break
        }
    }
}
for (int i = 1; i <= n; i ++ ) {
    cout << i << " " << way[i] << endl;
}

这样就完事了。
$$ 闫氏DP分析法 $$

1. 状态表示——集合：$f[i][j]$ 表示考虑前 $i$ 个公司，且花费总时间不超过 $j$ 的集合下能获得的最大价值。
2. 状态表示——属性：因为是求最大价值，故为 $max$。
3. 状态计算——集合划分：考虑第 $i$ 个公司给多少服务器。
   • 不选或选不了（剩余时间不够 $j < v[i]$）：$f[i - 1][j]$。
   • 选：$f[i - 1][j - k] + w[i][k]$。首先你对第i个物品进行了你的抉择，所以前一维变成了 $i - 1$，接着因为使用了 $k（枚举的）$ 的个数，所以应该是$j - v[i]$，最后你要把它带来的价值加上，所以要加上 $w[i][k]$。

完整代码，时间复杂度：$O(nm^2)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int n, m;
int f[N][N];
int w[N][N];
int way[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> w[i][j];
        }
    }
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j <= m; 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[n][m] << endl;

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