貪心演算法和分支限界法的比較

㈠ 0/1背包問題能不能使用貪心法解決

貪心演算法解決背包問題有幾種策略：
(i)一種貪婪准則為：從剩餘的物品中，選出可以裝入背包的價值最大的物品，利用這種規則，價值最大的物品首先被裝入（假設有足夠容量），然後是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮n=2, w=[100,10,10], p =[20,15,15], c = 105。當利用價值貪婪准則時，獲得的解為x= [ 1 , 0 , 0 ]，這種方案的總價值為2 0。而最優解為[ 0 , 1 , 1 ]，其總價值為3 0。
(ii)另一種方案是重量貪婪准則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規則對於前面的例子能產生最優解，但在一般情況下則不一定能得到最優解。考慮n= 2 ,w=[10,20], p=[5,100], c= 2 5。當利用重量貪婪策略時，獲得的解為x =[1,0], 比最優解[ 0 , 1 ]要差。
(iii)還有一種貪婪准則，就是我們教材上提到的，認為，每一項計算yi=vi/si,即該項值和大小的比，再按比值的降序來排序，從第一項開始裝背包，然後是第二項，依次類推，盡可能的多放，直到裝滿背包。
有的參考資料也稱為價值密度pi/wi貪婪演算法。這種策略也不能保證得到最優解。利用此策略試解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 時的最優解。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優解，但它是一個直覺上近似的解。
而且這是解決普通背包問題的最優解，因為在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

㈡ 演算法設計裡面分治法、貪心法、動態規劃法、回溯法、分枝限界法各是什麼意思

你這個問題問的內容太多了，還是看網路吧：
分治法：http://ke..com/view/1583824.htm?fr=aladdin
貪心演算法：http://ke..com/view/298415.htm
動態規劃：http://ke..com/view/28146.htm
回溯演算法：http://ke..com/view/6056523.htm
分支限界法：http://ke..com/view/4479359.htm

㈢ 大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系

《演算法分析與設計》是一門理論與應用並重的專業課程。本課程以演算法設計策略為知識單元，系統介紹計算機演算法的設計方法和分析技巧。課程主要內容包括:第1章，演算法概述；第二章，遞歸和分治策略；第三章，動態規劃；第四章，貪婪演算法；第五章，回溯法；第六章，分枝定界法。通過介紹經典實用的演算法，使學生掌握演算法設計的基本方法。結合案例分析，讓學生深入了解演算法設計的技巧和分析演算法的能力。

㈣ [演算法4] 哪個演算法比較難

當然是網路流啦，這個是研究生課題。。。

㈤ 編程語言中的五大經典演算法的異同點！！！

這樣說吧
分治和動態規劃都可看成原問題由子問題合成作用而得，只不過原、子問題結構關系分別是
樹型結構和有向無環圖

貪心是則可看成是鏈式結構

回溯和分支界限為窮舉式的搜索，其思想的差異是深度優先和廣度優先

㈥ dijakstra演算法和分支限演算法在解決單源最短路徑問題的異同

記dijakstra演算法為D演算法
D演算法為貪心演算法,每一步的選擇為當前步的最優,復雜度為O(n*n) (又叫爬山法)
分支限界演算法,每一步的擴散為當前耗散度的最優,復雜度為(沒算)

都是A演算法的極端情況
(說錯了哈,下面我的文字中的的分支限界演算法實際上是在說動態規劃法,我查了一下書,動態規劃法是對分支限界法的改進,分支限界法不屬於A演算法(啟發式搜索演算法),但是這時用動態規劃法和D演算法比較也是有可比性的,而直接用分支限界演算法和D演算法比較也是可以的)
關鍵詞:耗散度 評估函數
即:對當前優先搜索方向的判斷標准為,有可能的最優解
而最優解可以用一個評估函數來做,即已經有的耗散度加上以後有可能的耗度
A演算法就是把兩個耗散度加在一起,作為當前狀態的搜索搜索方向;
但是對以後的耗散度的評估是麻煩的,D演算法就是把當前有的路的最短的作為,以後耗散度的評估.
分支限界演算法就是只以以前的耗散度為評估函數

你給的兩個演算法當然是A演算法的特例
你還可以參考一下 A*演算法 修正的A*演算法,相信對你的編程水平有幫助

參考:
隊列式分支限界法的搜索解空間樹的方式類似於解空間樹的寬度優先搜索，不同的是隊列式分支限界法不搜索以不可行結點（已經被判定不能導致可行解或不能導致最優解的結點）為根的子樹。按照規則，這樣的結點不被列入活結點表。

優先隊列式分支限界法的搜索方式是根據活結點的優先順序確定下一個擴展結點。結點的優先順序常用一個與該結點有關的數值p來表示。最大優先隊列規定p值較大的結點點的優先順序較高。在演算法實現時通常用一個最大堆來實現最大優先隊列，體現最大效益優先的原則。類似地，最小優先隊列規定p值較小的結點的優先順序較高。在演算法實現時，常用一個最小堆來實現，體現最小優先的原則。採用優先隊列式分支定界演算法解決具體問題時，應根據問題的特點選用最大優先或最小優先隊列，確定各個結點點的p值。

㈦ C語言常用演算法分析的目錄

第1篇演算法基礎篇
第1章程序之魂——演算法
（ 自學視頻、源程序：
配套資源mr1） 2
1.1魂之說 3
1.2演算法的特性 4
1.3演算法的表示方式 5
1.3.1用自然語言描述演算法 5
1.3.2用流程圖描述演算法 5
1.3.3用N-S圖描述演算法 8
1.3.4用計算機語言描述演算法 9
1.4演算法性能分析與度量 10
1.4.1演算法的性能指標 10
1.4.2演算法效率的度量 10
1.4.3演算法的時間復雜度 11
1.4.4演算法的空間復雜度 12
1.5學習演算法的原因 12
第2章數據結構基礎
（ 自學視頻、源程序：
配套資源mr2） 13
2.1數據結構概述 14
2.1.1數據結構的發展 14
2.1.2數據結構的研究對象 14
2.1.3數據結構與演算法的關系 16
2.2數據結構的基本概念 16
2.3C語言常見數據結構 18
2.3.1數組 18
2.3.2結構體 20
2.3.3鏈表 21
2.3.4棧 23
2.3.5隊列 24
第3章查找與排序演算法
（ 自學視頻、源程序：
配套資源mr3） 26
3.1查找演算法 27
3.1.1順序查找 27
3.1.2折半查找 29
3.1.3分塊查找 31
3.1.4哈希查找 33
3.2排序演算法 38
3.2.1選擇排序 38
3.2.2冒泡排序 40
3.2.3直接插入排序 43
3.2.4歸並排序 45
3.2.5希爾排序 48
3.2.6快速排序 49
3.2.7各種排序演算法的比較 52
第4章基本演算法思想
（ 自學視頻、源程序：
配套資源mr4） 54
4.1遞歸的概念和分治法 55
4.1.1遞歸的概念 55
4.1.2遞歸的應用——漢諾塔 55
4.1.3分治法的基本思想 56
4.1.4分治法的應用——棋盤覆蓋
問題 57
4.2動態規劃法 59
4.2.1動態規劃法的基本思想 59
4.2.2動態規劃的應用——最大
子段和 60
4.3貪心演算法 61
4.3.1貪心演算法的基本概念 61
4.3.2貪心演算法的應用——哈夫
曼編碼 62
4.4回溯法 67
4.4.1回溯法的基本思想 67
4.4.2回溯法的應用——連續
郵資問題 68
4.5分支限界法 70
4.5.1分支限界法的基本思想 71
4.5.2分支限界法的應用——旅行
售貨員問題 71
第2篇常用演算法篇
第5章數學演算法
（ 自學視頻、源程序：
配套資源mr5） 76
5.1隨機數求π 77
5.2正態分布的成績 82
5.3繪制最小圓 86
5.4滿意的一元二次方程解 93
5.5計算定積分 101
5.6分解質因數 103
5.7最大公約數和最小公倍數 106
5.8數字的全排列 109
5.9遞推化梯形法求解定積分 111
5.10迭代法開平方運算 115
5.11牛頓切線法解方程 117
5.12改進歐拉方法求解微分方程 119
5.13迭代法求解線性方程組 123
5.14計算貸款利息 127
5.15分數計算器 129
第6章矩陣與數組問題
（ 自學視頻、源程序：
配套資源mr6） 132
6.1「脫殼」組數 133
6.2尋找矩陣中的「鞍點」 135
6.3魔幻方陣 137
6.4矩陣的轉置運算 139
6.5勾股數組 141
6.6百燈判熄 143
6.7巧排螺旋數陣 144
6.8猜數四問 146
第7章經典演算法
（ 自學視頻、源程序：
配套資源mr7） 149
7.1約瑟夫環 150
7.2八皇後問題 152
7.30-1背包問題 156
7.4斐波那契數列 159
7.5尋找水仙花數 161
7.6愛因斯坦階梯問題 162
7.7進制轉換演算法 163
7.8哥德巴赫猜想 165
7.9驗證四方定理 167
7.10尼科徹斯定理 168
7.11角谷猜想 170
7.12prim演算法求最小生成樹 171
7.13迪傑斯特拉演算法 174
第3篇趣味演算法篇
第8章數學趣題
（ 自學視頻、源程序：
配套資源mr8） 178
8.1警察抓犯人 179
8.2舍罕王的失算 181
8.3百錢買百雞問題 183
8.4三色球問題 185
8.5填數字游戲 187
8.6漁夫捕魚問題 190
8.7移數字游戲 191
8.8數字翻譯器 194
8.9猴子吃桃問題 198
8.10馬克思手稿中的數學題 199
8.11判斷迴文式素數 200
8.12完全數 204
8.13自守數 206
8.14一數三平方數 207
8.15古稀數 209
8.16親和數 213
8.17對調數 215
第9章邏輯推理題
（ 自學視頻、源程序：
配套資源mr9） 218
9.1魔術師的秘密 219
9.2婚禮上的謊言 220
9.3誰講了真話 222
9.4白紙與黑紙 223
9.5判斷壞球 224
9.6打漁曬網問題 229
9.7水池注水問題 231
9.8尋找假幣 232
9.9常勝將軍 234
9.10巧算國王分財物 236
9.11商人渡河問題 237
9.12馬踏棋盤 243
9.13猜杏核 246
第4篇演算法競技篇
第10章計算機等級考試演算法實例
（ 自學視頻、源程序：
配套資源mr10） 250
10.1數組的下三角置數 251
10.2查找單鏈表的結點 252
10.3二維數組的元素排序 254
10.4尋找二維數組的最大值 256
第11章程序員考試演算法實例
（ 自學視頻、源程序：
配套資源mr11） 258
11.1電話計費演算法 259
11.2處理鏈表的重復元素 261
11.3劇場方形空位 263
11.4數組的數值操作 265
11.5三位數生成迴文數 267
第12章信息學奧賽演算法實例
（ 自學視頻、源程序：
配套資源mr12） 269
12.1我知你心 270
12.2格雷碼 272
12.3狡猾的狐狸遇上聰明的兔子 275
12.46174問題 276
12.5韓信點兵 279
12.6楊輝三角 281
12.7開關燈問題 284
12.8蛇形方陣 286

㈧ 0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）

一.動態規劃求解0-1背包問題
/************************************************************************/
/* 0-1背包問題：
/* 給定n種物品和一個背包
/* 物品i的重量為wi，其價值為vi
/* 背包的容量為c
/* 應如何選擇裝入背包的物品，使得裝入背包中的物品
/* 的總價值最大？
/* 註：在選擇裝入背包的物品時，對物品i只有兩種選擇，
/* 即裝入或不裝入背包。不能將物品i裝入多次，也
/* 不能只裝入部分的物品i。
/*
/* 1. 0-1背包問題的形式化描述：
/* 給定c>0, wi>0, vi>0, 0<=i<=n，要求找到一個n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且滿足如下約束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包問題的求解
/* 0-1背包問題具有最優子結構性質和子問題重疊性質，適於
/* 採用動態規劃方法求解
/*
/* 2.1 最優子結構性質
/* 設(y1,y2,...,yn)是給定0-1背包問題的一個最優解，則必有
/* 結論，(y2,y3,...,yn)是如下子問題的一個最優解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因為如若不然，則該子問題存在一個最優解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最優解。那麼有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 進一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 這說明：(y1,z2,z3,...zn)是所給0-1背包問題的更優解，那麼
/* 說明(y1,y2,...,yn)不是問題的最優解，與前提矛盾，所以最優
/* 子結構性質成立。
/*
/* 2.2 子問題重疊性質
/* 設所給0-1背包問題的子問題 P(i,j)為：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 問題P(i,j)是背包容量為j、可選物品為i,i+1,...,n時的子問題
/* 設m(i,j)是子問題P(i,j)的最優值，即最大總價值。則根據最優
/* 子結構性質，可以建立m(i,j)的遞歸式：
/* a. 遞歸初始 m(n,j)
/* //背包容量為j、可選物品只有n，若背包容量j大於物品n的
/* //重量，則直接裝入；否則無法裝入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 遞歸式 m(i,j)
/* //背包容量為j、可選物品為i,i+1,...,n
/* //如果背包容量j<wi，則根本裝不進物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，則在不裝物品i和裝入物品i之間做出選擇
/* 不裝物品i的最優值：m(i+1,j)
/* 裝入物品i的最優值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//遞歸初始條件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}

for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}

//i從2到n-1，分別對j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}

m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}

}

template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}

int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;

int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}

int x[6];

Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);

return 0;
}
二.貪心演算法求解0-1背包問題
1.貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1).不能保證求得的最後解是最佳的；
2).不能用來求最大或最小解問題；
3).只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

2.例題分析

1).[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30

分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔空間最小的物品裝入是否能得到最優解？
（3）每次選取單位容量價值最大的物品，成為解本題的策略。

<程序代碼:>(環境:c++)
#include<iostream.h>
#define max 100 //最多物品數
void sort (int n,float a[max],float b[max]) //按價值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1為背包剩餘可裝載重量
int i;
sort(n,v,w); //物品按價值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]為1時，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"請輸入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品選擇情況表初始化為0
cout<<"請依次輸入物品的價值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"請依次輸入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的總重量為："<<totalw<<endl; //背包所裝載總重量
cout<<"背包的總價值為："<<totalv<<endl; //背包的總價值
}
三.回溯演算法求解0-1背包問題
1.0-l背包問題是子集選取問題。
一般情況下，0-1背包問題是NP難題。0-1背包
問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類
似。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當
右子樹有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。設r是當前剩餘
物品價值總和；cp是當前價值；bestp是當前最優價值。當cp+r≤bestp時，可剪去右
子樹。計算右子樹中解的上界的更好方法是將剩餘物品依其單位重量價值排序，然後
依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是
右子樹中解的上界。
2.解決辦法思路：
為了便於計算上界，可先將物品依其單位重量價值從大到小排序，此後只要順序考
察各物品即可。在實現時，由bound計算當前結點處的上界。在搜索解空間樹時，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。

回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
2.演算法框架：
a.問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
b.回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
3.運用回溯法解題通常包含以下三個步驟：
a.針對所給問題，定義問題的解空間；
b.確定易於搜索的解空間結構；
c.以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；
#include<iostream>

using namespace std;

class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );

public:
void print()
{

for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};

private:
int Bound(int i);
void Backtrack(int i);

int c;//背包容量
int n; //物品數
int *w;//物品重量數組
int *p;//物品價值數組
int cw;//當前重量
int cp;//當前價值
int bestp;//當前最優值
int *bestx;//當前最優解
int *x;//當前解

};

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;
}

void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子樹
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子樹
{
x[i]=0;
Backtrack(i+1);
}

}

class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}

private:
int ID;
float d;
};

int Knapsack(int p[],int w[],int c,int n)
{
//為Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//裝入所有物品
//依物品單位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}

}

Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;

}

void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包問題——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"請輸入背包容量(c)："<<endl;
cin>>c;
cout<<"請輸入物品的個數(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;

cout<<"請輸入物品的價值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];

cout<<"請輸入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];

cout<<"最優解為(bestx)："<<endl;
cout<<"最優值為(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新開始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包問題
1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。

2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。

#include <iostream.h>

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<number; i++)
{
cout<<"請輸入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"請輸入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout<<endl;
}

}

int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; 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<number; i++)//逐層遍歷解樹決定是否裝入各個物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍歷左子樹
upbound=bound_u;//更改已有u限界,不更改標志

if( getbound(i, &bound_u)>bound_c )//遍歷右子樹
//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//從已有重量和效益加上新物品
bag[i].flag=1;//標記為裝入
}
}

}

void Display()
{

cout<<"可以放入背包的物品的編號為：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}