01背包問題
經典的0 - 1背包問題的解決方案。

---

二維數組的版本

代碼功能概述

0 - 1背包問題指的是有 n 個物品和一個容量為 m 的背包，每個物品有對應的體積 v[i] 和價值 w[i]，需要從這些物品里挑選若干個放入背包，讓背包內物品的總價值達到最大。每個物品僅能選擇放入或者不放入背包（即0 - 1選擇）。

代碼詳細解釋

#include<bits/stdc++.h>
using namespace std;// 定義長整型別名
typedef long long LL;
// 定義數組的最大長度
const int N=1100;// f[i][j] 表示前 i 個物品，背包容量為 j 時的最大價值
int f[N][N];
// v[i] 表示第 i 個物品的體積，w[i] 表示第 i 個物品的價值
int v[N],w[N];int main(){// n 表示物品的數量，m 表示背包的容量int n,m;// 從標準輸入讀取物品數量和背包容量cin>>n>>m;// 循環讀取每個物品的體積和價值for(int i = 1;i<=n;i++){cin>>v[i]>>w[i];}// 動態規劃求解過程for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){// 如果當前背包容量 j 小于第 i 個物品的體積 v[i]，則不能放入第 i 個物品if(j < v[i])// 最大價值等于前 i - 1 個物品在容量 j 下的最大價值f[i][j] = f[i-1][j];else// 可以選擇放入或不放入第 i 個物品，取兩者中的最大值f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}}// 輸出前 n 個物品，背包容量為 m 時的最大價值cout<<f[n][m];return 0;
}

代碼核心邏輯

• 狀態定義：f[i][j] 代表前 i 個物品，背包容量為 j 時所能獲得的最大價值。
• 狀態轉移：
  • 若 j < v[i]，也就是當前背包容量不足以放入第 i 個物品，那么 f[i][j] = f[i - 1][j]。
  • 若 j >= v[i]，則可以選擇放入或者不放入第 i 個物品：
    • 不放入：f[i][j] = f[i - 1][j]。
    • 放入：f[i][j] = f[i - 1][j - v[i]] + w[i]。
  • 取這兩種情況的最大值作為 f[i][j] 的值。
• 最終結果：f[n][m] 即為前 n 個物品，背包容量為 m 時的最大價值。

復雜度分析

• 時間復雜度：$O(nm)$，這里的 n 是物品的數量，m 是背包的容量。
• 空間復雜度：$O(nm)$，主要是用于存儲狀態數組 f。

要將你的二維動態規劃代碼優化為一維數組，可以利用動態規劃的狀態轉移只依賴于上一行的狀態這一特性。通過從右到左更新一維數組，可以避免覆蓋還未使用的狀態，從而實現空間優化。

---

一維數組的版本

優化后的代碼

#include <bits/stdc++.h>
using namespace std;const int N = 1100;int f[N]; // 一維動態規劃數組，f[j] 表示湊出金額 j 所需的最大價值
int v[N], w[N]; // v[i] 表示第 i 個物品的體積，w[i] 表示第 i 個物品的價值int main() {int n, m;cin >> n >> m; // 輸入物品數量 n 和背包容量 mfor (int i = 1; i <= n; i++) {cin >> v[i] >> w[i]; // 輸入每個物品的體積和價值}// 初始化動態規劃數組memset(f, 0, sizeof(f)); // 初始時，所有金額的最大價值為 0// 動態規劃求解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]); // 更新狀態}}// 輸出結果cout << f[m] << endl; // 輸出湊出金額 m 的最大價值return 0;
}

---

代碼解釋

1. 一維數組的定義

• 原代碼使用二維數組 f[i][j] 表示前 i 個物品在背包容量為 j 時的最大價值。
• 優化后，使用一維數組 f[j] 表示背包容量為 j 時的最大價值。
• 因為狀態轉移只依賴于上一行的狀態，所以可以用一維數組代替二維數組。

2. 從右到左更新

• 在更新 f[j] 時，f[j - v[i]] 表示未選擇當前物品時的狀態。
• 如果從左到右更新（如 for (int j = v[i]; j <= m; j++)），會導致 f[j - v[i]] 被當前物品更新過，從而出現重復選擇當前物品的情況。
• 因此，必須從右到左更新（如 for (int j = m; j >= v[i]; j--)），確保每個物品只被選擇一次。

3. 狀態轉移方程

• 狀態轉移方程保持不變：
  $$f[j]=\max (f[j],f[j?v[i]]+w[i])$$
  • f[j] 表示不選擇當前物品時的最大價值。
  • f[j - v[i]] + w[i] 表示選擇當前物品時的最大價值。

4. 初始化

• 初始化 f 數組為 0，表示在沒有物品時，所有背包容量的最大價值都為 0。

5. 輸出結果

• 最終結果存儲在 f[m] 中，表示背包容量為 m 時的最大價值。

---

復雜度分析

時間復雜度

• 外層循環遍歷物品數量 $n$，內層循環遍歷背包容量 $m$。
• 時間復雜度為 $O(n\times m)$。

空間復雜度

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

---

注意事項

1. 從右到左更新的重要性：

   • 如果改為從左到右更新（如 for (int j = v[i]; j <= m; j++)），會導致每個物品被多次選擇，變成 完全背包問題 的解法。
   • 因此，在 0-1 背包問題 中，必須從右到左更新。

2. 適用場景：

   • 這段代碼適用于 0-1 背包問題，即每個物品只能選擇一次。
   • 如果是 完全背包問題（每個物品可以無限次選擇），需要將狀態轉移方程改為 f[j] = max(f[j], f[j - v[i]] + w[i])，并且內層循環改為從左到右更新。

---