AcWing 1013. 机器分配【分组背包+求方案数】

题目传送门

一、深度优先搜索

把\(m\)个机器分配给\(n\)个公司，暴力遍历所有方案

记录分配方案，如果能更新最优解，顺便更新一下最优解的分配方案

#include 

using namespace std;
const int N = 11; //最多N个公司
const int M = 16; //最多M个设备
int n;            //n个公司
int m;            //m个设备
int tmp[N];         //记录每一次尝试时的路径记录数组，但不一定是最优的，在达到最优时复制到path里
int w[N][M];      //第i个公司拿j个机器时获取到的价值
int Max;          //价值的最大值
int res[N];       //最佳的取法数组,一直记录到目前为止最优的方案

/**
 * 功能：深度优先搜索求最大值及方案
 * @param x     第x个公司
 * @param sum     总价值
 * @param r     剩余设备数量
 */
void dfs(int x, int sum, int r) {
    //如果走完了所有公司，就可以回头统计结果了
    if (x == n + 1) {
        //更新最大值
        if (sum > Max) {
            Max = sum;
            //复制保留当前最优路径
            for (int i = 1; i <= n; i++) res[i] = tmp[i];
        }
        return;
    }
    //从0到r(剩余机器数量),分别尝试分给第x个公司
    for (int i = 0; i <= r; i++) {
        tmp[x] = i;       //给第x个公司i个设备
        //开始尝试x+1个公司,此时价值增加了w[x][i],剩余机器数量减少了i
        dfs(x + 1, sum + w[x][i], r - i);
    }
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> m;
    //读入第i个公司，拿j个设备时的价值是多少
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> w[i][j];
    //爆搜
    dfs(1, 0, m);//站在第1个公司面前，爆搜，目前的总价值是0，剩余的机器数量是m
    //输出最大价值
    printf("%d\n", Max);
    //输出最大价值时的选择方法
    for (int i = 1; i <= n; i++)
        printf("%d %d\n", i, res[i]);
    return 0;
}

二、分组背包

#include 

using namespace std;
const int N = 30;

int n, m;       //n个公司，m个机器
int w[N][N];    //第i个公司，拿j个机器时可以得到的价值
int f[N][N];    //dp结果，第一维：前i个公司，第二维：在j个机器的情况下的最优解
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];//读入第i个公司，拿j个机器时能获取到的价值

    //二维分组背包模板（有细微修改s[i]->j）
    for (int i = 1; i <= n; i++)        // 枚举组
        for (int j = 0; j <= m; j++) {  // 枚举体积
            f[i][j] = f[i - 1][j];      // 一个都不选的情况,在本题其实不用考虑该情况,因为本题哪个公司不给机器，都不开心
            for (int k = 1; k <= j; k++)// 枚举物品,数量和价值在此统一到一起表示
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
        }
    //输出最大值
    printf("%d\n", f[n][m]);

    //求方案路径的套路
    int j = m;  //j代表空间大小
    for (int i = n; i >= 1; i--)        //倒序遍历每组，注意求解方案时需要从下向上
        for (int k = 0; k <= j; k++)    //看看f[i][j]是从哪个前序状态转化而来
            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++) printf("%d %d\n", i, way[i]);
    return 0;
}