# 回溯法與動態規劃在背包問題上的應用比較

## 前言
由於上課提及動態規劃解決背包問題，並以動態規劃(O(nw))做為舉例，再查找資料後後，
找到回溯法與其做對比較，分析優缺點以及應用情境，供各位所參考。
本文透過由ChatGpt4、參考資訊完成。
### 回溯法

回溯法是一種基於深度優先搜索的遞歸算法，盡可能的遍歷所有可能的解空間，尋找最優解。在遍歷過程中，當發現當前解無法達到最優解時，會回溯到上一個節點並繼續搜索。

簡單來說就是利用DFS+剪枝去做處理。

特點

時間複雜度高，為O(2^n)。在物品數量增加時，計算效率低。

### 動態規劃

動態規劃是一種將問題分解為子問題並將子問題的解存儲在表格中的方法。在背包問題中，動態規劃使用一個二維表格來存儲每個子問題的最優解。

特點

時間複雜度為O(nW)，相對於回溯法效率較高。

空間複雜度為O(nW)。當物品數量和背包容量都很大時，可能需要大量內存。
總之，回溯法和動態規劃法都可以解決背包問題。
然而，動態規劃通常具有較高的計算效率，尤其是在物品數量較多的情況下。然而，動態規劃需要較大的內存空間來存儲子問題的解。

### 特點比較

#### 回溯法：當物品數量較少，背包容量較大且內存需求低。

#### 動態規劃：當物品數量較多，背包容量不導致內存需求過高，且問題具有重疊子問題和最優子結構特性時，使用動態規劃法。

不同種類的背包問題：

回溯法：能較容易地應對價值和重量之間存在限制、優先級的背包問題。

如0-1背包問題、完全背包問題、多重背包問題...等。

動態規劃：需要更多以及複雜的操作去進行問題討論，進一步進行討論
### 實際操作
### 動態規劃
總體思路
根據動態規劃解題步驟（問題抽象化、建立模型、尋找約束條件、判斷是否滿足最優性原理、找大問題與小問題的遞推關係式、填表、尋找解組成）找出01背包問題的最優解以及解組成，然後編寫代碼實現。

#### 背包問題的解決過程
在解決問題之前，為描述方便，首先定義一些變量： Vi表示第i 個物品的價值，Wi表示第i 個物品的體積，定義V(i,j)：當前背包容量j，前i 個物品最佳組合對應的價值，同時背包問題抽象化（X1，X2，…，Xn，其中Xi 取0或1，表示第i 個物品選或不選）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、尋找約束條件，W1X1+W2X2+…+WnXn<capacity；

3、尋找遞推關係式，面對當前商品有兩種可能性：

包的容量比該商品體積小，裝不下，此時的價值與前i-1個的價值是一樣的，即V(i,j)=V(i-1,j)；
還有足夠的容量可以裝該商品，但裝了也不一定達到當前最優價值，所以在裝與不裝之間選擇最優的一個，即V(i,j)=max｛V(i-1,j)，V(i-1,jw(i))+v(i)｝。
其中V(i-1,j)表示不裝，V(i-1,jw(i))+v(i) 表示裝了第i個商品，背包容量減少w(i)，但價值增加了v(i)；

由此可以得出遞推關係式：

j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,jw(i))+v(i)｝
### 回溯法

計算每種物品單位重量的價值si=pi/wi
依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。
若將這種物品全部裝入背包後，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品並儘可能多地裝入背包。
依此策略一直地進行下去，直到背包裝滿為止。

參考資料：
https://blog.csdn.net/hanmo22357/article/details/124371395?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%9B%9E%E6%BA%AF%E6%B3%95%E8%A7%A3%E6%B1%BA%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-2-124371395.142^v76^pc_new_rank,201^v4^add_ask,239^v2^insert_chatgpt&spm=1018.2226.3001.4187