POJ 2184 Cow Exhibition：負權值 0/1 背包的座標平移技巧

題目大意

N 頭牛，每牛有智商 Sᵢ、幽默 Fᵢ（均可為負，範圍 [-1000, 1000]）。選擇子集使 ΣS ≥ 0、ΣF ≥ 0，最大化 ΣS + ΣF。

核心難點：背包容量與價值均可為負

標準 0/1 背包要求容量、價值非負。此處 Sᵢ 可視為「重量」，Fᵢ 為「價值」，兩者均可負，無法直接 DP。

座標平移：將負重量映射到非負索引

• 總智商範圍 [-1000N, 1000N]，但 N 實際較小（題目未給上限，原碼用 maxn=200000 覆蓋 ±100000）。
• 定義偏移 SHIFT = 100000（或足夠大的常數），將智商和 s 映射到索引 s + SHIFT。
• DP 陣列 dp[idx] 表示智商和為 idx - SHIFT 時的最大幽默和，初始 -INF，dp[SHIFT] = 0（智商 0、幽默 0）。

轉移方向取決於重量正負

對每頭牛 (w=Sᵢ, v=Fᵢ)：

• w ≥ 0：逆序 for (j = MAX; j ≥ w; --j)，防止同一物品重複使用（標準 0/1 背包）。
• w < 0：正序 for (j = 0; j ≤ MAX + w; ++j)。因 j - w > j，正序保證「當前輪」不覆蓋「上一輪」狀態（等價於負重量時從小索引向大索引轉移）。

答案提取

遍歷 idx = SHIFT .. MAX（智商 ≥ 0），若 dp[idx] ≥ 0（幽默 ≥ 0），更新 ans = max(ans, dp[idx] + (idx - SHIFT))。若 ans < 0 輸出 0。

複雜度

• 時間 O(N × MAX)，MAX ≈ 2×10⁵，N 較小（~20）可接受。
• 空間 O(MAX)。

關鍵洞察總結

1. 負重量 0/1 背包通過「座標平移 + 根據正負選擇迴圈方向」轉化為標準形式。
2. 平移量需覆蓋所有可能的負重量和，留足邊界。
3. 初始化 dp[SHIFT]=0 對應「選 0 項，重量 0、價值 0」。

總結

本題是「負權值背包」的經典教學案例。座標平移技巧將定義域擴展至非負整數，配合正負重量分別逆序/正序迴環，完美復用 0/1 背包框架。此思路廣泛適用於「狀態可為負」的 DP 問題（如股票交易手續費、溫度調節等）。