AcWing 1013. 機器配置設定

​​題目傳送門​​

一、深度優先搜尋

把\(m\)個機器配置設定給\(n\)個公司，暴力周遊所有方案

記錄配置設定方案，如果能更新最優解，順便更新一下最優解的配置設定方案

#include <bits/stdc++.h>

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 <bits/stdc++.h>

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個機器時能擷取到的價值

    //二維分組背包
    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++)//周遊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;
    for (int i = n; i >= 1; 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;
}