您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1837 Balance：多重背包計數求天平平衡方案數

編輯：關於C++

問題建模

天平有 C 個掛鉤（位置 -15~15，負為左臂、正為右臂），G 個砝碼（重量 1~25，互不相同）。每個砝碼必須掛在某個掛鉤上，求天平平衡（力矩和為 0）的方案數。力矩 = 重量 × 位置。最大單側力矩 15×20×25=7500，總範圍 [-7500, 7500]，平移後為 [0, 15000]，中心 7500 對應力矩 0。

動態規劃

dp[i][j]：使用前 i 個砝碼，力矩和偏移後為 j 的方案數。
初始：dp[0][7500] = 1（無砝碼時力矩 0）。
轉移：對第 i 個砝碼（重量 w = g[i]），枚舉掛鉤位置 pos = c[k]，力矩增量 delta = w * pos。
dp[i][j + delta] += dp[i-1][j]

最終答案 dp[G][7500]。

複雜度

狀態數：G ≤ 20，力矩範圍 15001。轉移每狀態枚舉 C ≤ 20 個掛鉤。
時間 O(G × 15000 × C) ≈ 6×10^6，空間 O(15000) 滾動數組優化至 1 維。

參考代碼（C++）

#include 
using namespace std;
const int OFFSET = 7500, MAXM = 15000;
int dp[2][MAXM + 1];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, G;
    while (cin >> C >> G) {
        vector hook(C), weight(G);
        for (int &x : hook) cin >> x;
        for (int &w : weight) cin >> w;
        fill(dp[0], dp[0] + MAXM + 1, 0);
        dp[0][OFFSET] = 1;
        int cur = 0, nxt = 1;
        for (int w : weight) {
            fill(dp[nxt], dp[nxt] + MAXM + 1, 0);
            for (int j = 0; j <= MAXM; ++j) if (dp[cur][j]) {
                for (int pos : hook) {
                    int nj = j + w * pos;
                    if (0 <= nj && nj <= MAXM)
                        dp[nxt][nj] += dp[cur][j];
                }
            }
            swap(cur, nxt);
        }
        cout << dp[cur][OFFSET] << '\n';
    }
    return 0;
}