CODEVS 3269 混合背包：01、完全、多重背包統一框架與優化去重

CODEVS 3269 混合背包：01、完全、多重背包統一框架與優化去重

題目大意

N 種物品，每種有體積 v、價值 w、數量 m（m=1 為 01 背包，m=-1 為完全背包，m>1 為多重背包）。背包容量 V。求最大價值。N ≤ 200, V ≤ 200,000。

核心優化：物品去重

若物品 i 被物品 j 完全支配（v_i ≥ v_j 且 w_i ≤ w_j），則 i 永遠不會被選，可刪除。規則：

• 01 背包 (m=1) 被完全背包 (m=-1) 或多重背包 (m>1) 支配 → 刪除。
• 多重背包 (m>1) 被完全背包 (m=-1) 支配 → 刪除。

去重後物品數大幅減少，避免 TLE。

三種背包統一處理框架

void zero_pack(int cost, int weight) { // 01 背包
    for (int j = V; j >= cost; --j) f[j] = max(f[j], f[j-cost] + weight);
}
void complete_pack(int cost, int weight) { // 完全背包
    for (int j = cost; j <= V; ++j) f[j] = max(f[j], f[j-cost] + weight);
}
void multi_pack(int cost, int weight, int amount) { // 多重背包（二進制拆分）
    if (cost * amount >= V) { complete_pack(cost, weight); return; }
    int k = 1;
    while (k < amount) {
        zero_pack(cost * k, weight * k);
        amount -= k; k <<= 1;
    }
    zero_pack(cost * amount, weight * amount);
}

完整主程式

int main() {
    int n = read(), V = read();
    // 讀入 v[i], w[i], m[i]
    // 去重標記 vis[i]
    for (int i = 1; i <= n; ++i)
        for (int j = i+1; j <= n; ++j)
            // 根據 m[i], m[j] 判斷支配關係，標記 vis

    for (int i = 1; i <= n; ++i) {
        if (m[i] == 1 && !vis[i]) zero_pack(v[i], w[i]);
        else if (m[i] == -1) complete_pack(v[i], w[i]);
        else if (!vis[i]) multi_pack(v[i], w[i], m[i]);
    }
    write(f[V]);
    return 0;
}

快速 IO 實作

使用自訂 read()、write() 替代 cin/cout，大幅提升輸入輸出速度，對大數據量至關重要。

複雜度分析

• 去重：O(N^2)，N≤200 可接受。
• DP：去重後有效物品數 M ≪ N，總操作數 ≈ Σ (V / v_i) ，通過優化可在時限內通過。