1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個隻能全放入或者不放入，求解如何放入物品，可以使背包裡的物品的總效益最大。
2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，并用結點上界殺死不符合要求的結點。
#include
struct good
{
int weight;
int benefit;
int flag;//是否可以裝入标記
};
int number=0;//物品數量
int upbound=0;
int curp=0, curw=0;//目前效益值與重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i {
cout<>bag[i].weight;
cout<>bag[i].benefit;
bag[i].flag=0;//初始标志為不裝入背包
cout< }
}
int getbound(int num, int *bound_u)//傳回本結點的c限界和u限界
{
for(int w=curw, p=curp; num {
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//目前結點的c限界和u限界
for(int i=0; i {
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//周遊左子樹
upbound=bound_u;//更改已有u限界,不更改标志
if( getbound(i, &bound_u)>bound_c )//周遊右子樹
◆◆
評論讀取中....
請登入後再發表評論!
◆◆
修改失敗，請稍後嘗試