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

🔗 P1616 疯狂的采药

Problem Statement

題目簡述

有一段固定的採藥時間，以及若干種草藥。
每種草藥都有採摘一次所需的時間與可獲得的價值，且每種草藥可以重複採摘任意次。
求在總時間限制內，最多能獲得多少價值。

Constraints

約束條件

  • 1≤T≤1071 \le T \le 10^7，其中 TT 為總時間。
  • 1≤M≤1041 \le M \le 10^4，其中 MM 為草藥種類數。
  • 1≤T×M≤1071 \le T \times M \le 10^7
  • 1≤ai,bi≤1041 \le a_i, b_i \le 10^4，其中 aia_i 為採摘第 ii 種草藥所需時間，bib_i 為採摘第 ii 種草藥可獲得的價值。

思路：完全背包 DP

這題和一般 0/1 背包最大的差別在於：同一種草藥可以採很多次。也就是說，當我們決定某種草藥值得採時，它不只可能出現一次，而是可以在剩餘時間允許的情況下反覆被選取。

如果用暴力枚舉每種草藥要採幾次，組合數會非常大，尤其總時間上限很高，無法逐一嘗試。因此需要用動態規劃把「某個時間容量下的最佳價值」記錄下來，避免重複計算。

狀態設計與轉移

用一個答案陣列記錄：在不超過某段採藥時間時，目前能取得的最大價值。

對於每一種草藥，我們嘗試把它放進不同的時間容量中。若目前容量足以採摘這種草藥，就可以比較兩種選擇：

  • 不採這次草藥，維持原本最佳價值。
  • 採這次草藥，並把剩下時間的最佳價值加上這次取得的價值。

取兩者較大值，就是目前時間容量下的新最佳答案。

為什麼要由小到大更新？

完全背包允許同一種草藥重複採摘，所以在處理同一種草藥時，後面的容量應該能使用前面容量剛更新出的結果。

如果像 0/1 背包一樣由大到小更新，每種草藥在一輪中最多只會被使用一次，會錯誤地變成 0/1 背包。

複雜度分析

  • 時間複雜度：O(MT)\mathcal{O}(MT)
  • 空間複雜度：O(T)\mathcal{O}(T)

Code

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

    # f[i][j] 表示考慮前 i 個物品，時間為 j 時的最大價值
    f = [0] * (t + 1)
    for v, w in items:
        for j in range(v, t + 1):
            f[j] = max(f[j], f[j - v] + w)
    print(f[t])


if __name__ == "__main__":
    solve()