這段代碼實現了一個多重背包問題的動態規劃解法。多重背包問題與完全背包問題類似，但每個物品有其數量限制。以下是代碼的詳細思路解析：

---

1. 問題背景

給定 n 個物品，每個物品有其體積 v[i]、價值 w[i] 和數量 s[i]，以及一個容量為 m 的背包。目標是選擇物品使得總價值最大，同時總容量不超過背包的容量。與完全背包問題不同的是，多重背包問題中每個物品的數量是有限的。

2. 動態規劃的概念

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

3. 代碼邏輯解析

(1) 輸入數據

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

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

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

(2) 動態規劃狀態轉移

for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++)for (int k = 0; k <= s[i] && k * v[i] <= j; k++)f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

1. 外層循環：

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

2. 中層循環：

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

3. 內層循環：

   • 遍歷每個物品可以被選擇的次數 k，從 0 到 s[i]（即當前物品的最大數量），并且確保 k * v[i] <= j（即當前容量可以容納的最大次數）。

4. 狀態轉移：

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

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

   • 選擇第 i 個物品 k 次：更新 f[i][j] 為 f[i - 1][j - v[i] * k] + w[i] * k，即前 i-1 個物品在容量為 j - v[i] * k 的背包下的最大價值加上第 i 個物品的價值乘以選擇次數 k。

(3) 輸出結果

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

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

4. 代碼效率分析

• 時間復雜度：

  • 三層循環遍歷所有物品、所有容量和所有選擇次數，時間復雜度為 O(n × m × s_max)，其中 s_max 是最大的物品數量。

• 空間復雜度：

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

5. 示例運行

輸入：

4 5
1 2 3
2 4 1
3 4 3
4 5 2

輸出：

10

6. 總結

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

完整代碼

#include<bits/stdc++.h>
using namespace std;// 定義常量 N 作為數組的最大長度
const int N = 110;
// n 表示物品的種類數，m 表示背包的容量
int n, m;
// v 數組存儲每種物品的體積，w 數組存儲每種物品的價值，s 數組存儲每種物品的數量上限
int v[N], w[N], s[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] >> s[i];// 動態規劃過程，外層循環遍歷每種物品for(int i = 1; i <= n; i ++)// 中層循環遍歷背包的所有可能容量for(int j = 0; j <= m; j ++)// 內層循環枚舉當前物品 i 放入的數量 k，k 要滿足不超過該物品的數量上限 s[i] 且放入 k 個物品后的體積不超過當前背包容量 jfor(int k = 0; k <= s[i] && k * v[i] <= j; k ++)// 比較當前記錄的最大價值 f[i][j] 和放入 k 個第 i 種物品后的價值// 放入 k 個第 i 種物品后，剩余容量為 j - v[i] * k，之前 i - 1 種物品在該剩余容量下的最大價值為 f[i - 1][j - v[i] * k]// 放入 k 個第 i 種物品的價值為 w[i] * kf[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);// 輸出前 n 種物品，背包容量為 m 時能獲得的最大價值cout << f[n][m] << endl;return 0;
}