這段代碼實現了一個經典的0-1 背包問題的動態規劃解法。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 = 0; j <= m; j++){f[i][j] = f[i - 1][j];  // 不選擇第 i 個物品if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);  // 選擇第 i 個物品}

1. 外層循環：

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

2. 內層循環：

   • 遍歷背包的每個容量，從 0 到 m。

3. 狀態轉移：

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

   • 不選擇第 i 個物品：f[i][j] = f[i - 1][j]，即前 i-1 個物品在容量為 j 的背包下的最大價值。

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

(3) 輸出結果

cout << f[n][m] << endl;

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

4. 代碼效率分析

• 時間復雜度：

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

• 空間復雜度：

  • 使用了一個二維數組 f，空間復雜度為 O(n × 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][j] = 0，表示沒有物品時的最大價值為 0。

   • 對于第 1 個物品：

     • f[1][0] = 0

     • f[1][1] = 2

     • f[1][2] = 2

     • f[1][3] = 2

     • f[1][4] = 2

     • f[1][5] = 2

   • 對于第 2 個物品：

     • f[2][0] = 0

     • f[2][1] = 2

     • f[2][2] = 3

     • f[2][3] = 5

     • f[2][4] = 5

     • f[2][5] = 5

   • 對于第 3 個物品：

     • f[3][0] = 0

     • f[3][1] = 2

     • f[3][2] = 3

     • f[3][3] = 5

     • f[3][4] = 6

     • f[3][5] = 7

輸出：

7

6. 總結

這段代碼的核心思路是通過動態規劃解決 0-1 背包問題。通過維護一個二維數組 f，記錄不同狀態下的最大價值，并通過狀態轉移方程更新最大價值，最終找到在給定背包容量下的最大價值。這種方法的時間復雜度為 O(n × 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[i][j] 表示前 i 個物品，背包容量為 j 時能獲得的最大價值
int f[N][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 ++)// 內層循環遍歷背包的所有可能容量for(int j = 0; j <= m; j ++){// 不選擇第 i 個物品，那么前 i 個物品在容量為 j 的背包中的最大價值// 就等于前 i - 1 個物品在容量為 j 的背包中的最大價值f[i][j] = f[i - 1][j];// 如果當前背包的容量 j 大于等于第 i 個物品的體積 v[i]// 說明可以選擇放入第 i 個物品if(j >= v[i]) // 比較不放入第 i 個物品和放入第 i 個物品兩種情況下的最大價值// 放入第 i 個物品的價值為 f[i - 1][j - v[i]] + w[i]f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}// 輸出前 n 個物品，背包容量為 m 時能獲得的最大價值cout << f[n][m] << endl;return 0;
}