題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 AT_dp_e Knapsack 2

Problem Statement

題目簡述

有 NN 個物品，每個物品重 wiw_i 價值 viv_i。求在總重量不超過 WW 的限制下，能獲得的最大總價值。

Constraints

約束條件

  • 1≤N≤1001 \le N \le 100
  • 1≤W≤1091 \le W \le 10^9
  • 1≤wi≤W1 \le w_i \le W
  • 1≤vi≤1031 \le v_i \le 10^3

思路：轉換狀態定義

標準 0/1 背包的複雜度為 O(NW)O(NW)，但本題 WW 高達 10910^9，直接套用會超時且記憶體不足。

關鍵觀察

題目給出 N≤100N \le 100 且 vi≤103v_i \le 10^3，因此總價值上界僅為 Vmax⁡=N⋅max⁡(vi)=105V_{\max} = N \cdot \max(v_i) = 10^5。

這啟發我們交換 DP 的狀態與目標：

標準背包 本題做法
dp[w] = max_value dp[v] = min_weight
固定重量，求最大價值 固定價值，求最小重量

DP 定義

狀態定義

f[v]：恰好達成總價值 vv 所需的最小總重量。

轉移方程

對於每個物品 (wi,vi)(w_i, v_i)，從大到小枚舉價值 jj：

f[j]=min⁡(f[j],  f[j−vi]+wi)f[j] = \min\bigl(f[j],\; f[j - v_i] + w_i\bigr)

初始化與答案

  • 初始化：f[0]=0f[0] = 0，其餘為 ∞\infty。
  • 答案：滿足 f[v]≤Wf[v] \le W 的最大 vv。

複雜度分析

  • 時間複雜度：O(N⋅Vmax⁡)\mathcal{O}(N \cdot V_{\max})，約 10710^7 次運算。
  • 空間複雜度：O(Vmax⁡)\mathcal{O}(V_{\max})，約 10510^5 大小的陣列。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solve():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    # f[v] 表示當購買的價值為 v 時，所需的最小重量
    V = sum(v for _, v in items)
    f = [float("inf")] * (V + 1)
    f[0] = 0
    for w, v in items:
        for j in range(V, v - 1, -1):
            f[j] = min(f[j], f[j - v] + w)
    print(max(i for i, w in enumerate(f) if w <= W))

if __name__ == "__main__":
    solve()