#include
#include
#include
#define?N?100
using?namespace?std;
class?HeapNode
{
????public:
????????float?uprofitprofitweight;
????????int?levelx[N];
};
stack?H;
float?w[N]p[N];
float?cwcp;
int?ncbestx[100];
float?Bound（int?i）
{
????float?cleft=c-cwb=cp;
????while（i<=n&&w[i]<=cleft）
????{
????????cleft-=w[i];
????????b+=p[i];
????????i++;
????????bestx[i]=1;
????}
????if（i<=n）??b+=p[i]/w[i]*cleft;
????return?b;
}
void?AddLiveNode（float?upfloat?cpfloat?cwbool?chint?level）
{
????HeapNode?nod;
????nod.uprofit=up;
????nod.profit=cp;
????nod.weight=cw;
????nod.level=level;
????if（level<=n）??H.push（nod）;
}
int?Knap（）
{
????int?i=1;
????cw=cp=0;
????float?bestp=0up=Bound（1）;
????while（1）
????{
????????float?wt=cw+w[i];
????????if（wt<=c）
????????{
????????????if（cp+p[i]>bestp）???bestp=cp+p[i];
????????????AddLiveNode（upcp+p[i]cw+w[i]truei+1）;
????????}
????????up=Bound（i+1）;
????????if（up>=bestp）
?????????????AddLiveNode（upcpcwfalsei+1）;
????????if（H.empty（））???return?bestp;
????????HeapNode?node=H.top（）;
????????H.pop（）;
????????cw=node.weight;
????????cp=node.profit;
????????up=node.uprofit;
????????i=node.level;
????}
}
int?main（）
{
????printf（“輸入背包容量:\n“）;
????scanf（“%d“&c）;
????while（c<0）
????{
?????????printf（“請輸入合法數據:\n“）;
????scanf（“%d“&c）;
????}
????printf（“輸入物品數量:\n“）;
????scanf（“%d“&n）;
????while（n<0）
????{
?????????printf（“請輸入合法數據:\n“）;
????scanf（“%d“&n）;
????}
????FILE?*fp;
????fp=fopen（“data1.txt““r“）;
???for（int?i=1;i<=n;i++）
???{
???????fscanf（fp“%f“&w[i]）;
???????fscanf（fp“%f“&p[i]）;
???}
???cout<<“物品質量分別為：“;
???for（int?i=1;i<=n;i++）
???{
???????cout<???}
???cout<???cout<<“物品價值分別為：“;
???for（int?i=1;i<=n;i++）
???{
???????cout<???}
???cout<?????for（int?i=1;i<=n;i++）
????????bestx[i]=0;
???fclose（fp）;printf（“0-1背包問題最優值:\n“）;
????printf（“%d\n“Knap（））;
????printf（“0-1背包問題最優解\n“）;
????for（int?i=1;i<=n;i++）
????????printf（“%d?“bestx[i]）;
????printf（“\n“）;

????fp=fopen（“data2.txt““w“）;

????????fprintf（fp“0-1背包問題最優值：%d\n?“Knap（））;
????????fprintf（fp“0-1背包問題最優解：“）;
???????????for（int?i=1;i<=n;i++）
????fprintf（fp“%d?“bestx[i]）;

????fclose（fp）;

????return?0;}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-11-26?19:26??0-1背包-分支限界\
?????文件????????2396??2016-12-05?21:15??0-1背包-分支限界\0-1.cpp
?????文件??????985740??2016-12-05?21:15??0-1背包-分支限界\0-1.exe
?????文件???????44071??2016-12-05?21:15??0-1背包-分支限界\0-1.o
?????文件??????????23??2016-12-05?20:28??0-1背包-分支限界\data1.txt
?????文件??????????52??2016-12-05?21:13??0-1背包-分支限界\data2.txt
?????文件???????10288??2016-12-05?21:24??0-1背包-分支限界\測試用例_.xlsx
?????文件???????63298??2016-12-05?21:24??0-1背包-分支限界\說明+流程圖.docx
?????目錄???????????0??2018-11-26?19:26??0-1背包-動態規劃\
?????文件????????1663??2016-12-05?18:02??0-1背包-動態規劃\0-1背包.cpp
?????文件??????959845??2016-12-05?18:08??0-1背包-動態規劃\0-1背包.exe
?????文件????????5227??2016-12-05?18:08??0-1背包-動態規劃\0-1背包.o
?????文件??????????15??2016-12-05?18:08??0-1背包-動態規劃\data1.txt
?????文件??????????48??2016-12-05?18:10??0-1背包-動態規劃\data2.txt
?????文件???????10224??2016-12-05?18:12??0-1背包-動態規劃\測試用例.xlsx
?????文件???????65140??2016-12-05?18:29??0-1背包-動態規劃\說明+流程圖.docx
?????目錄???????????0??2018-11-26?19:26??0-1背包-回溯法\
?????文件??????????23??2016-12-05?20:28??0-1背包-回溯法\data1.txt
?????文件??????????53??2016-12-05?21:02??0-1背包-回溯法\data2.txt
?????文件????????1583??2016-12-05?21:14??0-1背包-回溯法\回溯.cpp
?????文件??????959345??2016-12-05?21:02??0-1背包-回溯法\回溯.exe
?????文件????????3629??2016-12-05?21:02??0-1背包-回溯法\回溯.o
?????文件???????10285??2016-12-05?20:32??0-1背包-回溯法\測試用例_.xlsx
?????文件???????69362??2016-12-05?20:50??0-1背包-回溯法\說明+流程圖.docx