這段代碼實現了0-1 背包問題的動態規劃解法，并且使用了滾動數組來優化空間復雜度。以下是代碼的詳細思路解析：

---

1. 問題背景

給定 n 個物品，每個物品有其體積 v[i] 和價值 w[i]，以及一個容量為 m 的背包。目標是選擇物品使得總價值最大，同時總容量不超過背包的容量。

2. 動態規劃的概念

動態規劃是一種常用的算法技巧，用于解決具有重疊子問題和最優子結構的問題。在 0-1 背包問題中，動態規劃通過維護一個一維數組 f 來記錄不同狀態下的最大價值。

3. 代碼邏輯解析

(1) 輸入數據

cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

• 用戶輸入物品數量 n 和背包容量 m。

• 對于每個物品，輸入其體積 v[i] 和價值 w[i]。

(2) 動態規劃狀態轉移

for (int i = 1; i <= n; i++)for (int j = m; j >= v[i]; j--)f[j] = max(f[j], f[j - v[i]] + w[i]);

1. 外層循環：

   • 遍歷每個物品，從第 1 個到第 n 個。

2. 內層循環：

   • 遍歷背包的每個容量，從 m 到 v[i]（逆序遍歷）。

   • 逆序遍歷的原因是避免重復使用同一個物品。如果正序遍歷，同一個物品可能會被多次使用，從而變成完全背包問題。

3. 狀態轉移：

   • f[j] 表示在容量為 j 的背包下的最大價值。

   • 不選擇第 i 個物品：f[j] 保持不變。

   • 選擇第 i 個物品：如果當前容量 j 大于等于第 i 個物品的體積 v[i]，則可以考慮選擇第 i 個物品，更新 f[j] 為 f[j - v[i]] + w[i]，即在容量為 j - v[i] 的背包下的最大價值加上第 i 個物品的價值。

(3) 輸出結果

cout << f[m] << endl;

• 輸出最終的最大價值，即 f[m]。

4. 代碼效率分析

• 時間復雜度：

  • 兩層循環遍歷所有物品和所有容量，時間復雜度為 O(n × m)。

• 空間復雜度：

  • 使用了一個一維數組 f，空間復雜度為 O(m)。

5. 示例運行

輸入：

3 5
1 2
2 3
3 4

運行過程：

1. 輸入數據：

   • n = 3, m = 5

   • v = [1, 2, 3], w = [2, 3, 4]

2. 動態規劃狀態轉移：

   • 初始化 f 數組為 0。

   • 對于第 1 個物品：

     • f[5] = max(f[5], f[4] + 2) = 2

     • f[4] = max(f[4], f[3] + 2) = 2

     • f[3] = max(f[3], f[2] + 2) = 2

     • f[2] = max(f[2], f[1] + 2) = 2

     • f[1] = max(f[1], f[0] + 2) = 2

   • 對于第 2 個物品：

     • f[5] = max(f[5], f[3] + 3) = 5

     • f[4] = max(f[4], f[2] + 3) = 5

     • f[3] = max(f[3], f[1] + 3) = 5

     • f[2] = max(f[2], f[0] + 3) = 3

   • 對于第 3 個物品：

     • f[5] = max(f[5], f[2] + 4) = 7

     • f[4] = max(f[4], f[1] + 4) = 6

     • f[3] = max(f[3], f[0] + 4) = 4

輸出：

7

6. 總結

這段代碼的核心思路是通過動態規劃解決 0-1 背包問題，并使用滾動數組優化空間復雜度。通過維護一個一維數組 f，記錄不同狀態下的最大價值，并通過狀態轉移方程更新最大價值，最終找到在給定背包容量下的最大價值。這種方法的時間復雜度為 O(n × m)，空間復雜度為 O(m)，適用于中等規模的 0-1 背包問題。

完整代碼

#include<bits/stdc++.h>
using namespace std;// 定義數組的最大長度
const int N = 1010;
// n 代表物品的數量，m 代表背包的容量
int n, m;
// v 數組用來存儲每個物品的體積，w 數組用來存儲每個物品的價值
int v[N], w[N];
// f 數組是一維數組，f[j] 表示背包容量為 j 時能獲得的最大價值
int f[N];int main()
{// 輸入物品的數量 n 和背包的容量 mcin >> n >> m;// 循環讀入每個物品的體積和價值for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];// 動態規劃過程，外層循環遍歷每個物品for(int i = 1; i <= n; i ++)// 內層循環從背包的最大容量 m 開始，遞減到當前物品的體積 v[i]for(int j = m; j >= v[i]; j --)// 比較不選擇第 i 個物品和選擇第 i 個物品兩種情況下的最大價值// 不選擇第 i 個物品時，f[j] 保持不變// 選擇第 i 個物品時，價值為 f[j - v[i]] + w[i]f[j] = max(f[j], f[j - v[i]] + w[i]);// 輸出背包容量為 m 時能獲得的最大價值cout << f[m] << endl;return 0;
}