【背包】
今天來講講背包問題
背包問題是DP問題的一種，
而DP問題離不開三個特性：
- 最優子結構
- 無后效性
- 重疊子問題
在講背包問題之前，我們先講講斐波那契數列，
總所周知斐波那契數列的遞推公式是
F(n)=F(n-1)+F(n-2)
但是我們可以畫個圖看看，在使用遞回求解斐波那契數列第N項的時候會發生什么問題
寫到這里應該就很清楚了，我們要求F（n）一定要遞回求得F（n-1）和F（n-2），但是我們在求F（n-1）的時候，我還需要再遞回求一個F（n-2），那么時間的開銷就變大了許多許多，這就是上面DP說的重疊子問題，我重復地求了一個值，以至于當n很大很大地時候接近葉子節點地上一層地資料被計算了相當多次，這時間地開銷是非常非常大的，而且我們從時間復雜度的角度出發，這個演算法本身也是O(2^n)，
那么，我們從節省時間的角度我們去解決一下斐波那契數列，既然我們重復地計算了某一個值，那我們能不能用一個變數先存放他在那，直到用的時候，我才把他調度出來，也就是說，我們從n=2開始我們用for回圈遞進的方式，一個一個地求出前n-1項地值，那么我們在計算第n項地值得時候，我們就可以之間從陣列中通過下標索引得方式去得到F（n-1）和F（n-2）從而計算出F（n）的值，
這里我就不進行代碼實作了，
我們回歸到今天的主角：背包問題
有N件物品和一個容量為V的背包，每種物品均只有一件， 第i件物品的質量是w[i]，價值是c[i]，求解將哪些物品裝入背包可使這些物品的質量總和不超過背包容量，且價值總和最大，
在本題中，乍一看，好像沒有思路，或者有的同學會覺得性價比方案可以解決背包問題
我們一步步來仿照剛剛的斐波那契數列的O（n）求解法
第一步
我們先完成簡單的輸入，把緩沖區的資料全部讀進一個陣列中，并按照價值，升序排序
struct object {
int val;
int weight;
};
//這里是存盤的資料型別
int main() {
int T;
//T代表著我有多少個物體
while (cin >> T) {
int weight = 0;
cin >> weight;
object* Arr = new object[T];
for (int count = 0; count < T; count++) cin >> Arr[count].val >> Arr[count].weight;
//input
//sort
for (int count = 0; count < T; count++) {
for (int j = count+1; j < T; j++) {
if (Arr[count].val > Arr[j].val) {
//change
object tem = Arr[count];
Arr[count] = Arr[j];
Arr[j] = tem;
}
}
}
}
}
這里用了冒泡排序增強可讀性，我們也可以用其他更快速的排序去減少時間的復雜度，不過這不屬于我們的核心代碼塊
我們這里直接定義一個函式名為DP_bag
圖解如下
于是我們便有遞回實作的代碼
int DP_bag(object *Arr,int Value,int weight,int last){
if (last < 0)return 0;//裝不下了
else if (weight < Arr[last].weight)return DP_bag(Arr, Value, weight, last - 1);//裝不下最貴的，往后找
else return max(DP_bag(Arr, Value, weight, last - 1), Arr[last].val +DP_bag(Arr, Arr[last].val + Value, weight - Arr[last].weight, last - 1));
}
找到最優子結構和重疊子問題后就可轉換
我們先設定一個Dp陣列，為了避免多次計算重疊的子問題，我們可以用一個DP陣列來存盤每一個值
int DP_bag(object* Arr, int T,int weight) {
int* DP = new int[weight+1];
memset(DP, 0, weight+1);//T3RSCG
for (int i = 0; i < T; i++) {
for (int j = weight; j >= Arr[i].weight; j--) {
DP[j] = max(DP[j], DP[j - Arr[i].weight] + Arr[i].val);
}
}
return DP[weight];
}
我們來解剖一下這段代碼，在DP陣列中，J表示的是目前的程重，而第一層回圈遍歷了所有的物體，第二次回圈則是根據每次物體的屬性更新他的值，因此我們只需要回傳當程重等于給定程重時候的最大價值即可
上一段的解釋有點粗糙，可能會讓一部分的同學看不懂這段代碼，但是暫時只能先寫到這里，以后有更好的理解再進行修改（因為我太菜了）
總結一下把，該類的背包問題其實是屬于01背包問題
在以二進制為主導數制的計算機中，0往往代表著低電平，1代表著高電平，
回歸到該問題，我們無非離不開判斷（放/不放），也就是1 與 0之間的關系，
01背包問題，也就因此得名
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/181405.html
標籤：其他
上一篇：(比賽回顧)廣工大2020級年ACM第一次月賽–Problem G: 秧歌Star不要上補習班
下一篇：關于游戲開發入門指南