POJ 1018 Communication System：動態規劃求最大帶寬價格比

問題描述

公司需建立通信系統，需要 n 種設備，第 i 種設備有 m_i 家廠商提供。每家廠商的設備有帶寬 b 與價格 p。每種設備選一件，使整體系統的 B/P 最大，其中 B 為所選設備的最小帶寬，P 為總價格。

解法分析

本題可用 DP、搜尋、貪心、三分法等多種方法。此處講解動態規劃思路。

狀態定義

dp[i][j] 表示選擇前 i 種設備，系統帶寬為 j 時的最小總價格。

轉移方程

對於第 i 種設備的每個選項（帶寬 b，價格 p）：

dp[i][j] = min(dp[i][j], dp[i-1][k] + p)

其中新帶寬 j = min(k, b)。

DP 程式碼實作

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
int dp[120][1200];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        // 初始化
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < 1100; j++)
                dp[i][j] = INF;

        for (int i = 1; i <= n; i++) {
            int num;
            scanf("%d", &num);
            for (int j = 1; j <= num; j++) {
                int p, b;
                scanf("%d%d", &b, &p);
                if (i == 1) {
                    dp[1][b] = min(dp[1][b], p);
                } else {
                    for (int k = 0; k < 1100; k++) {
                        if (dp[i-1][k] != INF) {
                            if (k <= b)
                                dp[i][k] = min(dp[i][k], dp[i-1][k] + p);
                            else
                                dp[i][b] = min(dp[i][b], dp[i-1][k] + p);
                        }
                    }
                }
            }
        }

        double ans = 0;
        for (int i = 0; i < 1100; i++) {
            if (dp[n][i] != INF) {
                double ratio = (double)i / dp[n][i];
                if (ratio > ans) ans = ratio;
            }
        }
        printf("%.3lf\n", ans);
    }
    return 0;
}

貪心思路補充（正確性待驗證）

從第一種設備的每個選項開始，每次向下貪心選擇使整體 B/P 最大的選項，最終取最大值。有興趣者可自行驗證正確性。