資源簡介
用回溯法解0_1背包問題時，會用到狀態(tài)空間樹。在搜索狀態(tài)空間樹時，只要其左兒子結(jié)點是一個可行結(jié)點，搜索就進(jìn)入其左子樹。當(dāng)右子樹有可能包含最優(yōu)解時才進(jìn)入右子樹搜索，否則將右子樹剪去。設(shè)r是當(dāng)前剩余物品價值總和；cp是當(dāng)前價值；bestp是當(dāng)前最優(yōu)價值。當(dāng)cp+r≤bestp時，可剪去右子樹。計算右子樹中解的上界可以用的方法是將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是右子樹中解的上界，用此值來剪枝。
為了便于計算上界，可先將物品依其單位重量價值從大到小排序，此后只要順序考察各物品即可。在實現(xiàn)時，由MaxBoundary函數(shù)計算當(dāng)
代碼片段和文件信息
#include
using?namespace?std;
?
?
class?Knap
{
friend?int?Knapsack（int?p[]int?w[]int?cint?n?）;
?
public:
void?print（）
{
???? for（int?m=1;m<=n;m++）
?{
if（m%10==0）?printf（“\n“）;
printf（“%-4d“bestx[m]）;
?}
printf（“\n“）;
?};
?
private:
??int?Bound（int?i）;
??void?Backtrack（int?i）;
?
??int?c;//背包容量
??int?n;?//物品數(shù)
??int?*w;//物品重量數(shù)組
??int?*p;//物品價值數(shù)組
??int?cw;//當(dāng)前重量
??int?cp;//當(dāng)前價值
??int?bestp;//當(dāng)前最優(yōu)值
??int?*bestx;//當(dāng)前最優(yōu)解
??int?*x;//當(dāng)前解
?
};
?
//?**************?Bound（）?計算上界?********************************
int?Knap::Bound（int?i）?
{
?int?cleft=c-cw;//剩余容量
?int?b=cp;
?//以物品單位重量價值遞減序裝入物品
?while（i<=n&&w[i]<=cleft）
?{
???cleft-=w[i];
???b+=p[i];
???i++;
?}
?//裝滿背包
?if（i<=n）
??b+=p[i]/w[i]*cleft;
?return?b;
}
?
//?*****?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2012-12-04?22:40??0_1背包回溯法\
?????文件????????2861??2012-12-04?22:38??0_1背包回溯法\0_1背包回溯法.cpp
?????文件????????3487??2012-12-04?14:59??0_1背包回溯法\0_1背包回溯法.dsp
?????文件?????????551??2012-12-04?22:38??0_1背包回溯法\0_1背包回溯法.dsw
?????文件???????41984??2012-12-04?22:38??0_1背包回溯法\0_1背包回溯法.ncb
?????文件???????48640??2012-12-04?22:38??0_1背包回溯法\0_1背包回溯法.opt
?????文件?????????773??2012-12-04?22:38??0_1背包回溯法\0_1背包回溯法.plg
?????目錄???????????0??2012-12-04?22:40??0_1背包回溯法\Debug\
?????文件??????548970??2012-12-04?22:38??0_1背包回溯法\Debug\0_1背包回溯法.exe
?????文件??????788892??2012-12-04?22:38??0_1背包回溯法\Debug\0_1背包回溯法.ilk
?????文件??????253772??2012-12-04?22:38??0_1背包回溯法\Debug\0_1背包回溯法.obj
?????文件?????1997944??2012-12-04?14:59??0_1背包回溯法\Debug\0_1背包回溯法.pch
?????文件?????1098752??2012-12-04?22:38??0_1背包回溯法\Debug\0_1背包回溯法.pdb
?????文件???????74752??2012-12-04?22:38??0_1背包回溯法\Debug\vc60.idb
?????文件??????110592??2012-12-04?22:38??0_1背包回溯法\Debug\vc60.pdb
評論
共有 條評論