❶ 分支定界法 0-1多背包問題
的動態規劃0-1背包問題
/ ************************************* *********************************** /
/ * 0-1背包問題： /> / * n種物品和一個背包
/ *項目無線網路，我的體重VI的價值
/ *背包的容量為c
/ *應該如何選擇項目載入背包使物品裝入背包
/ *總最看重的嗎？
/ *註：選擇項目裝入背包的物品我只有兩個選擇
/ *載入或不裝入背包。我不能載入多個
/ *不能只是載入的項目。
/ *
/ * 1。 0-1背包問題的形式化描述：
/ * C> 0，無線網路> 0，六0，0 <= I <= N要求找到一個n
/ * 0-1向量（ X1，X2，...，XN），使得：
/ *最大sum_ {= 1到n}（ⅵ*ⅹⅰ），並滿足下面的約束：
/ *（1）sum_ {I = 1到n}（WI *十一）<= C
/ *（2）十一∈{0，1} 1 <= I <= N
/ * ...... / a>
/ * 2。
/ * 0-1背包問題0-1背包問題的解決有重疊的性質的最優子結構性質和子適合
/ *使用動態規劃方法解決
/
/ * 2.1最優子結構性質
/ *設置（Y1，Y2，...，yn）的0-1背包問題，最佳的解決方案，它肯定
> / *結論（Y2，Y3，...，yn）的是下面的子問題的最優解：
/ *最大sum_ {i = 2到n}（VI *十一）
/ *（1）sum_ {i = 2到N}（WI *十一）<= C - W1 * Y1
/ *（2）十一∈{0，1}，2 <= I <= N /> / *否則，子問題有一個最優的解決方案（Z2，Z3，...，zn的），
/ *（Y2，Y3，...，yn）的比的最優解。然後：
/ * sum_ {i = 2到n}（VI *子）sum_ {i = 2到n}（VI *易）
/ *，W1 * Y1 + sum_ {i = 2到n}（WI *子）<= C
/ *進一步指出：
/ * V1 * Y1 + sum_ {i = 2到n}（VI *子）> sum_ {i = 1 N}（VI *易）
/ * W1 * Y1 + sum_ {i = 2到n}（無線ZI）<= C
/ *這說明：（Y1，Z2，Z3， ，...，ZN）0-1背包問題是一個更好的解決方案，然後
/ *說明（Y1，Y2，...，yn）的是不矛盾的前提下，最佳的解決方案，因此，最好
/ *建立的子結構的性質。
/ *
/ * 2.2子重疊性質
/ *設置給定的0-1背包問題的子P（I，J）：
/ *最大sum_ {K = I N}（VK * XK）
/ *（1）sum_ {K = I為n}（周* XK）<= J
/ *（2）XK∈{0，1}， I <= K <= N
/ * P（I，J）的問題是背包容量為j，可選的項目我，我+1，...，n的子的問題
/ *設M（I，J）是子P（I，J），最大總價值的最優值。在最佳
/ *子結構的性質可以創建遞歸米的（I，J）：
/ *。遞歸的初始M（N，J）
/ * / /背包容量為j，可選的項目只有n，，如果背包容量j是大於項目?
/ / /重量直接載入;無法載入。
/ * M（N，J）= VN，J> = WN
/ * M（N，J）= 0，0 <= J <WN
/ * B。遞推公式M（I，J）
/ * / /背包容量?，可選的項目我，我+1，...，N
/ * / /背包容量J <無線網路，後來乾脆不安裝成的文章：
/ * M（I，J）= M（I +1，J），0 <= j的無線
/ * / / J> =無線網路，文章中，我載入的項目之間我選擇
/ *沒有我的最佳值：M（i +1，j）的安裝項目
/ *載入項，我的最優值：M（i +1， J-WI）+ VI
/ *：
/ * M（I，J）= {M（I +1，J），M（I +1，J-無線）+ VI}，J> =無線
/ *
/ ***************************** ******************************************* /
/>
定義MAX（A，B）（（（一）（二））（A）（B））
定義分（A，B）（ （（A）（B））（A）（B））
模板
無效背包（類型* V，INT * W，C，N，類型* * M）
{
/ /遞歸的初始條件
詮釋JMAX = MIN（W [N] - 1，C）;
（J = 0;? <= JMAX J + +）{
米[N] [J] = 0;
}
（J = W [N]; <= C; J + +）{
M [N] [J] = V [N];
}
/ /我從2到n-1，分別為j> = wi和0 <= j的無線M（I，J）
（INT I = N-1; i> 1的，我 - ）{
JMAX = MIN（W [我] - 1，C）;
（J = 0; <= JMAX; J + +）{
M [] [J] = M [+1] [J]; ...... />}
為（J = W [I]; <= C; + +）{
M [] [J] = MAX（M [+1] [J]， M [+1] [JW [我] + V [I]）;
}
}
M [1] [C] = M [2] [ C];
（C> = W [1]）{
M [1] [C] = MAX（M [1] [C]，M [2] [CW [1]] + V [1]）;
}
}
模板
無效回溯（類型**米，INT * W， INT整數N，C，* X）
{
為（int i = 1; <N，我+ +）{
（M [] [C] == M [+1] [C]）×[I] = 0;
其他{
×[我] = 1;
C - = W [I];
}
}
×[N] =（M [N] [C]）？ 1:0;
}
：（INT ARGC，字元*的argv []）
{
廉政n = 5;
>詮釋W [6] = {-1，2，2，6，5，4};
INT V [6] = {-1，6，3，5，4，6};
>詮釋C = 10;
** ppm =百新詮釋[N +1];
（INT I = 0; I <N +1，我+ +）{
PPM [] =新的int [C +1];
}
詮釋x [6];
背包的（V ，W，C，N，PPM）;
：回溯的（ppm時，W，C，N，X）;
返回0;}
貪心演算法求解0-1背包問題
的基本思路？貪婪的方法：
逐漸接近目標，給予盡可能快地獲得一個更好的解決方案在地上 - 從最初的解決方案的問題。當達到一個演算法的步驟不能繼續向前走，演算法停止。
的演算法問題：
1）不能保證獲得最終的解決方案;
2）不能被用來謀求最大或最小解決方案;
3）尋求滿足一定的約束條件，可行的解決方案。
演算法：
開始從最初的解決方案的問題;
獲得可行的解決方案提出了總體目標，而移動元素的解決方案;
所有解決方案組件組合成一個可行的解決方案的問題;
2實例分析
1）。背包問題，背包，背包容量是M = 150。 7物品時，物品可分為任意的尺寸。的
要求盡可能多，以使總價值的物品裝入背包，但不能超過總容量。
的項ABCDEFG
權重值35 30 60 50 40 10 25
10 40 30 50 35 40 30
：
目標函數： σpi，
約束裝入的物品的總重量計不超過背包容量：Σwi<= M（M = 150）
（1）根據貪心策略，每個選定的值最大的裝載物品的背包，得到的結果是最優的？
（2）每次選擇負載最小的項目可以得到最佳的解決方案嗎？
（3）每次你選擇一個單位容量的最有價值的項目，解決這個問題的戰略。
（環境：C + +）
包括與ltiostream.h的>
＃定義最大100 / /最大數量的項目
無效排序（N，飄起了[MAX]，持股量B [MAX]）/ /密度值的排序
{
整數J，H，和K;
持股量T1，T2， T3，C [MAX];
（k = 1時，K <= N，K + +）
?[K] = [K] / B [K]
（H = 1，H <N，H + +）
（J = 1，J <= NH J + +）
（C [J] C [j +1]中）
{T1 = A [J]，A [J] = A [j +1]中的[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;
>}
}
無效背包（INT N，持股量limitw，浮動V [MAX]，浮瓦特[MAX]，詮釋x [MAX]）
{浮動C1 / / C1背包剩餘的負載重量
我
排序（N，V，W）/ /排序價值密度的
C1 = limitw
為（i = 1我=我+ +）
{
（W [I]> C1）打破;
×[我] = 1; / / x [我]的文章我了解
C1 = C1-W [I];
}
}
無效的主要（）
{N，I，X [MAX];
>浮法V [MAX]，W [MAX]，totalv = 0，totalw = 0，limitw;
法院<<「請輸入n和limitw：」
CIN >> N >> limitw
為（i = 1; <=我+ +）
×[我] = 0; / /初始化為0的產品選擇表
法院<<「請進入價值的項目依次：「<< endl;
（i = 1; <=我+ +）
CIN >> V [I];
法院<; <endl;
法院<<「請輸入的重量反過來的項目：」<< endl;
（i = 1; <= N; + +）
CIN >> W [I];
法院<< endl;
背包（N，limitw，V，W，X）;
法院<<「選擇的是：」
>（i = 1; <= N; + +）
{
法院<< X [I];
（X [I] == 1） totalw = totalw + W [I];
}
法院<< endl;
法院<<「總重量的背包：<<totalw << endl; / /背包裝載總重量
法院<<「總價值的背包為：的」「totalv << endl; / /背包的總價值
}
三回溯演算法0 -1背包問題
1.0-l背包問題是選定的子集的問題。
一般,0-1背包問題是NP-難的。
0-1背包解決方案的可用空間的一個子集樹。
喜歡回溯0-1背包問題裝載問題的回溯是非常一流。搜索解空間樹的搜索，只要其左子節點是一個可行的節點，進入其左子樹。
右子樹可能只包含右子樹搜索的最佳解決方案，否則，切右子樹。設r其餘
商品的價值的總和;陰極保護電流值;當前最優值bestp。
子樹可以削權當CP + R≤bestp。在右子樹的上限解的計算是更好的方法，其餘項目根據其單位重量排序的值
然後在打開載入項直到合適的，然後到的文章充滿背包。得到的值是上限
右子樹的解決方案。
2。解決方案的想法：
為了便於計算中上的第一個項目，每單位重量的約束根據降序自己的價值，並此後，只要測試的順序
可以觀察到的各種物品。在實現綁定在當前節點的上限計算。搜索解決方案空間樹，只要其左子節點是一個可行的節點，搜索到的左子樹，右子樹可能含有進入右子樹搜索的最佳解決方案之前，否則，切右子樹。
回溯跳躍系統的搜索演算法。它包含了所有問題的解空間樹的解決方案，根據深度優先的策略，開始從根本上搜索解空間樹。總是首先確定節點的解決方案不包含樹演算法搜索的解空間中的任何節點。當然不包含跳層和它的祖先節點的節點是根的子樹的搜索回溯系統，否則，進入子樹，繼續深入搜索優先策略。回溯所有使用的解決方案，提出了一個問題，我們必須回頭去根，根的子樹搜索，直到結束。回溯，用乞求的問題，任何一個解決方案，只要搜索一個解決問題的辦法可以結束了。被稱為回溯的深度優先搜索演算法的問題的解決方案，它適用於了解一些大量的組合。
2。演算法框架： BR />問題的解空間：應用回溯法解決問題，首先應該明確的定義問題的解決空間問題的解空間中至少包含一個（最佳）的解決方案。
B。回溯基本思想是：以確定的組織結構對空間的理解，回溯從開始節點（根），深度優先搜索整個解空間的起始節點成為一個活結點，也是當前擴展節點。在當前的擴展結中，搜索到的深度方向移動到一個新的節點。新的節點是一個新的活結點，和目前的擴張節點，如果當前的交界處延長不能進一步移動，在深度方向上，那麼當前的擴展結點死鎖。換言之，此節點不再是一個活結點，在這一點上，應該向後移動（回溯）指向一個活結活結擴展節點停止回溯這樣的遞歸地搜索解空間中工作，直到你找到解決方案或解決方案所需的空間活結點。
3。用回溯法解決問題通常是由以下三個步驟：
解決方案的空間一個給定的問題，定義問題;
B。確定易於搜索的解空間結構;
C。深度優先的方式搜索解空間，並在搜索過程中通過修剪功能，以避免無效搜索;
＃包括
使用命名空間std;
類雷德克納普
{
朋友整數背包（P []，詮釋W []，詮釋三，廉政n）;
：
無效的print（）
{
（M = 1，M <= N，M + +）
{
法院<< bestx [M] <<「」;
}
法院<< endl;
};
私人如下：
整數約束（int i）的;
無效回溯（int i）的;
詮釋三;/ /背包容量
廉政n，/ /項目數
詮釋* W / /菜單項權重數組
詮釋* p ;/ /項目值的數組
詮釋CW ;/ /重量
INT CP ;/ /電流值
詮釋bestp ;/ /當前的最優值
詮釋* bestx ;/ /當前最優解
詮釋*
}
詮釋雷德克納普::綁定（一）
{
/ /計算x ;/ /當前的解決方案上限
詮釋裂= C-CW ;/ /剩餘容量
INT B = CP;
/ /項目單位重量價值遞減的序列載入項
（I <= N &&瓦特[I] <=裂）
{
裂= W [I]
B + = [];
+ +;
>}
/ /填充背包
如果（i <= N）
B + = [I] / W [I] *裂;
回報B; ...... />}
無效雷德克納普::回溯（一）
{
如果（I>）
{
（ bestp <CP）
{
（J = 1; <= N; + +）
bestx [J] = [J]。
bestp = CP
}
回報;
}
（CW + W [I] <= C）/ /搜索左子樹
{
×[我] = 1;
CW + = W [I];
CP + = [];
回溯 - 觸控板（i +1）;
CW - = W [I];
CP-= P [I];
}
如果「（綁定（i +1）> bestp）/ /搜索右子樹
{ BR /> x [I] = 0;
回溯 - 觸控板（i +1）;
}
}
>類對象
{
朋友整數背包（P []，詮釋W []，詮釋三，廉政n）;
內部操作符<=（對象A ）常量
{
回報率（D> =廣告）;
}
私人如下：
整數ID;
浮動D; />};
整數背包（P []，詮釋W []，詮釋三，廉政n）
{
/ /為雷德克納普： ：Backtrack面板 - 觸控板初始化
詮釋W = 0;
詮釋P = 0;
INT I = 1;
對象* Q =新的對象[N]; / a>（I = 1; <=我+ +）
{
Q [I-1]。ID =我;
Q [I-1]，D = 1.0 * P [I] / W [I];
P + = [];
W + = W [I];
}
（W <= C）
回報P ;/ /載入的所有項目
/ /按產品單位重量排序
浮F;
為（i = 0; I <N;我+ +）
（整數J = I，J <N; J + +）
{
（Q [I]，D <Q [J]。四）
{ BR /> F = Q [I]，D;
Q [我]，D = Q [J]。天;
Q [J]。D = F;
}
a>
}
雷德克納普K;
KP =新的int [N +1];
KW =新的int [N +1];
KX = INT [N +1];
K.bestx =新的int [N +1];
KX [0] = 0;
K.bestx [0 ] = 0;
為（i = 1; <= N; + +）
{
KP [I] = P [Q [I-1]。ID]; BR /> KW [我] = W [Q [I-1]。ID];
}
K.cp = 0;
K.cw = 0;
KC = C;
KN = N;
K.bestp = 0;
/ /回溯搜索
K.Backtrack（）;
K.print的（）
刪除[] Q;
刪除[]千瓦;
刪除[] KP;
回報K.bestp;
}
無效的主要（）
{
* P;
* W;
整數C = 0;
廉政n = 0;
> INT I = 0;
字元K表;
法院<<「0-1背包問題 - 回溯」<< endl;
法院<<「通過zbqplayer <而（K）
{
法院<<「請輸入一個背包容量（C）：」<< endl;
CIN >> C;
法院<<「請輸入的項目數（n）：「<< endl;
CIN >> N
P =新的int [N +1];
W =新的int [ +1];
P [0] = 0;
W [0] = 0;
法院<<「請輸入一個值（P）的項目： << endl;
（i = 1; <= N; + +）
CIN >> P [I];
法院<<「請輸入項目的重量（W）：「<< endl;
為（i = 1; <=我+ +）
CIN >> W [I]
BR />法院<<「最佳的解決方案（bestx）：」<< endl;
法院<<「最佳的值（bestp）：」<< endl;
的cout <<背負的（P， W，C，N）<< endl;
法院<<「[S]重新啟動」<< endl;
法院<<「[q]退出」<< endl; BR /> CIN >> K
}
四個分支定界法求解0-1背包問題
問題描述：已知的N項和一個背包可以容納M個權重，權重我的體重，只認沽或不投入，解決如何把在背包中的物品的總收益的項目，可以使每一個項目。
2。設計的思考和分析：選擇的項目，或不構成解決方案樹，左子樹不載入，正確的說，節點負載，以獲得最佳的樹檢索問題的解決辦法謝界殺不符合要求的節點。
包括
結構良好
{
詮釋權重;
詮釋的利益;
INT標志;/ /是否載入標簽
};
整型數= 0 ;/ /項目數
詮釋upbound = 0;
詮釋curp = 0，curw = 0 ;/ /當前實際價值和重量
詮釋maxweight = 0;
好包= NULL;
的虛空Init_good（）{
>袋=新好[數字];
（INT I = 0;我數，我+ +）
{
法院<<「請輸入第一塊「。 ;「<< i +1 <<」重的項目：「
CIN >>袋[i]的重量;
法院<<」請輸入片「<< i +1 << 「項目的好處：」
CIN >>袋[I]。利益;
袋[I]。標志= 0 ;/ /初始標志沒有被裝入背包
法院<< endl;
}
}
詮釋getbound（整數民， * bound_u）/ /返回節點c計和壓力表ü
{
（瓦特= curw，P = curp，民數&&（W +包[NUM]重量）<= maxweight NUM + +）
{
W = W +包[NUM]。重量;
P = W +包[NUM]。效益;
}
* bound_u = P +包[NUM]。 ，效益;
回報（P +包[NUM]。利益（（maxweight-W）/袋[NUM]。重量））;
}
無效LCbag（）
{
bound_u = 0，bound_c = 0 ;/ /當前節點c方向和u和約束
（i = 0;號碼;我+ +層）/ /層穿越解決方案，樹，以決定是否載入不同的項目
{（I +1，及bound_u））>
（（bound_c =的getbound upbound）/ /遍歷左子樹
upbound = bound_u ;/ /改變有U計不會改變的標志
如果「（getbound（I＆bound_u）> bound_c）/ /遍歷右子樹
/ /如果載入，以確定是否大於左子樹的根的右子樹C標尺C標尺負載
{的
upbound = bound_u ;/ /變化有u和約束
curp = curp +包[I]。利益的
curw = curw +包[i]的重量;/ /重量和效益從現有再加上新的項目
袋[I]。標志= 1; / /標記載入
}
}
}
顯示（）
{
/> COUT <<「項目可放置在背包里數：」;
（INT I = 0;我數，我+ +）
（袋[I]。標志> 0 ）
法院<< i +1 <<「」;
法院<< endl;
刪除[]袋;
}
❷ 有關語言的問題
算上n次就行了
❸ 裝載問題的貪心選擇性質如何證明
設箱子重量從小到大（x1,x2,...,xn），若集合A是最優裝載問題的一個最優解。A中第一個箱子為k。若k=1，A就是一個滿足貪心性質的最優解。假如當k>1，令B=A-{k}+{1},因為Wk>=W1,則B中的總重量小於等於A中的總重量，A是最優解，則B也是最優解，而B是選擇以箱子1為開始的最優解。可知總存在以貪心選擇開始的最優解。
❹ 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;
}
❺ C語言關於裝載問題（背包問題）的一個程序 我寫的程序輸出不滿足題意 但我檢查不出來錯誤 希望大神解決
想法:是先讓c1船盡量裝貨物是可以的，但是演算法應該不對，可以用下面的演算法
// 前k個數中去任意個數，且這些數之和為s的取法是否存在
int main()
{
int n, i, k1, k2, s, u;
cin >> n;
for (i=1; i<=2*n; i++)
cin >> A[i];
int sum = 0;
for (i=1; i<=2*n; i++)
sum += A[i];
memset(dp,0,sizeof(dp));
dp[0][0]=true;
// 外階段k1表示第k1個數，內階段k2表示選取數的個數
for (k1=1; k1<=2*n; k1++) // 外階段k1
{
for (k2=k1; k2>=1; k2--) // 內階段k2
for (s=1; s<=sum/2; s++) // 狀態s
{
//dp[k1][s] = dp[k1-1][s];
// 有兩個決策包含或不包含元素k1
if (s>=A[k1] && dp[k2-1][s-A[k1]])
dp[k2][s] = true;
}
}
// 之前的dp[k][s]表示從前k個數中取任意k個數，經過下面的步驟後
// 即表示從前k個數中取任意個數
for (k1=2; k1<=2*n; k1++)
for (s=1; s<=sum/2; s++)
if (dp[k1-1][s]) dp[k1][s]=true;
// 確定最接近的給定值sum/2的和
for (s=sum/2; s>=1 && !dp[2*n][s]; s--);
}
❻ 貪心演算法的最優裝載問題
void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)
1.void loading(int W[],int X[],int c,int n)
2.沒有定義i;
3.for（;;）是冒號，非逗號
❼ 最優裝載：有一批集裝箱要裝上一艘載重量為totalW的輪船，其中集裝箱i的重量為wi。最有裝載問題要求在裝在
453453