生活随笔
收集整理的這篇文章主要介紹了
回溯应用-- 0-1背包问题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1. 問題描述
0-1背包非常經典，很多場景都可以抽象成這個問題。經典解法是動態規劃，回溯簡單但沒有那么高效。
- 有一個背包，背包總的承載重量是 W kg。現有n個物品，每個物品重量不等，并且不可分割。
- 選擇幾件物品，裝到背包中。在不超過背包所能裝載重量的前提下，如何讓背包中物品總重量最大？
- 物品是不可分割的，要么裝要么不裝，所以叫 0-1背包問題。
2. 回溯解決思路
- 對于每個物品來說，都有兩種選擇，裝進背包或者不裝進背包。
- 對于n個物品來說，總的裝法就有 2n 種，去掉總重量超過 W kg的，從剩下的裝法中選擇總重量最接近 W kg的。不過，我們如何才能不重復地窮舉出這 2n 種裝法呢？
可以用回溯方法。
- 把物品依次排列，整個問題就分解為了n個階段，每個階段對應一個物品怎么選擇。
- 先對第一個物品進行處理，選擇裝進去或者不裝進去，然后再遞歸地處理剩下的物品。
- 當發現已經選擇的物品的重量超過 W kg之后，就停止繼續探測剩下的物品(搜索剪枝技巧)。
#include <iostream>
#define MaxWeight 76
using namespace std
;
void fill(int i
, int curWeight
, int *bag
, int N
, int &maxweightinbag
)
{if(curWeight
== MaxWeight
|| i
== N
){if(curWeight
> maxweightinbag
)maxweightinbag
= curWeight
;return;}fill(i
+1,curWeight
,bag
,N
,maxweightinbag
);if(curWeight
+bag
[i
] <= MaxWeight
){fill(i
+1,curWeight
+bag
[i
],bag
,N
,maxweightinbag
);}
}
int main()
{const int N
= 4;int bag
[N
] = {15,6,40,21};
int maxweightinbag
= 0;fill(0,0,bag
,N
,maxweightinbag
);cout
<< "最大可裝進背包的重量是：" << maxweightinbag
;return 0;
}
升級版：
每個物品對應著一種價值，求不超過背包載重極限，可裝入背包的最大總價值。（在上面程序里稍加修改即可）
#include <iostream>
#define MaxWeight 50
using namespace std
;
void fill(int i
, int curWeight
, int curValue
, int *bag
,int *value
, int N
, int &weightinbag
, int &maxValue
)
{if(curWeight
== MaxWeight
|| i
== N
){if(curValue
> maxValue
){maxValue
= curValue
;weightinbag
= curWeight
;}return;}fill(i
+1,curWeight
,curValue
,bag
,value
,N
,weightinbag
,maxValue
);if(curWeight
+bag
[i
] <= MaxWeight
){fill(i
+1,curWeight
+bag
[i
],curValue
+value
[i
],bag
,value
,N
,weightinbag
,maxValue
);}
}
int main()
{const int N
= 4;int bag
[N
] = {15,6,40,21};int value
[N
] = {1,2,3,4};int weightinbag
= 0, maxValue
= 0;fill(0,0,0,bag
,value
,N
,weightinbag
,maxValue
);cout
<< "最大可裝進背包的最大價值是：" << maxValue
<< " ,對應重量是: " << weightinbag
;return 0;
}
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的回溯应用-- 0-1背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
