背包規劃演算法

Ⅰ 貪心演算法 部分背包問題

這道題是dp的思想啦，動態規劃

(1)背包問題最優值的結構

動態規劃的逆向思維法的第一步是刻畫一個最優值的結構，如果我們能分析出一個問題的最優值包含其子問題的最優值，問題的這種性質稱為最優子結構。一個問題的最優子結構性質是該問題可以使用動態規劃的顯著特徵。

對一個負重能力為m的背包，如果我們選擇裝入一個第 i 種物品，那麼原背包問題就轉化為負重能力為 m-w[i] 的子背包問題。原背包問題的最優值包含這個子背包問題的最優值。若我們用背包的負重能力來劃分狀態，令狀態變數s[k]表示負重能力為k的背包，那麼s[m]的值只取決於s[k](k≤m)的值。因此背包問題具有最優子結構。

(2)遞歸地定義最優值

動態規劃的逆向思維法的第二步是根據各個子問題的最優值來遞歸地定義原問題的最優值。對背包問題而言，有狀態轉移方程：

／max{s[k-w[i]]+v[i]}(其中1≤i≤n，且k-w[i]≥0)

s[k]= 若k>0且存在1≤i≤n使k-w[i]≥0，

＼ 0 否則。

有了計算各個子問題的最優值的遞歸式，我們就可以直接編寫對應的程序。下述的函數knapsack是輸入背包的負重能力k，返回對應的子背包問題的最優值s[k]：

Ⅱ 用動態規劃演算法怎樣求解01背包問題

動態規劃主要解決的是多階段的決策問題。

01背包中，狀態為背包剩餘的容量，階段是每一個物品，決策是是否選擇當前的物品。

所以用動態規劃來解決是非常貼切的。

我們設f[V]表示已經使用容量為V時所能獲得的最大價值，w[i]表示i物品的質量，c[i]表示i物品的價值。

for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);

這便是所謂的一個狀態轉移方程。

f[j]表示在已經使用容量為j時的最大價值，f[j-w[i]]表示在已經使用容量為j-w[i]時的最大價值。

f[j]可以由f[j-w[i]]這個狀態轉移到達，表示選取w[i]這個物品，並從而獲得價值為c[i]。

而每次f[j]會在選與不選中決策選出最優的方案。

從每一個物品，也就是每一個階段的局部最優推出最後的全局最優值。這樣就解決了01背包問題

Ⅲ 關於C++ 01背包問題

1.摘要

以背包問題為例，介紹了貪心法與動態規劃的關系以及兩個方案在解決背包問題上的比較。貪心法什麼時候能取到最優界並無一般理論，但對於普通背包問題我們有一個完美的結果——貪心法可取到最優解。介紹了其它一些對背包問題的研究或者拓展。

2.介紹

貪心演算法是我們在《演算法設計技巧與分析》這門課中所學習到的幾種重要的演算法之一，顧名思義，貪心演算法總是作出在當前看來最好的選擇。也就是該演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的從局部的最優選擇，尋找到解決問題的次優解的方法。雖然我們希望貪心演算法得到的最終結果也是整體最優的，但是在某些情況下，該演算法得到的只是問題的最優解的近似。

3.演算法思想:

貪心法的基本思路：

——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。

該演算法存在問題：

1.不能保證求得的最後解是最佳的；

2.不能用來求最大或最小解問題；

3.只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：

在約束下最大。

(2)動態規劃解決方案：是解決0/1背包問題的最優解

(i)若i=0或j=0,V[i,j] = 0

(ii)若j<si, V[i,j] = V[i-1,j](僅用最優的方法，選取前i-1項物品裝入體積為j的背包，因為第i項體積大於j,裝不下這一項，所以背包裡面的i-1項就達到最大值)

(iii)若i>0和j>=si, Max{V[i-1,j],V[i-1,j-si]+vi} (第一種情況是包中的i-1項已經達到最大值，第二種情況是i-1項佔j-si的體積再加上第i項的總的價值，取這兩種情況的最大值。)

//sj和vj分別為第j項物品的體積和價值，C是總體積限制。

//V[i,j]表示從前i項{u1,u2,…,un}中取出來的裝入體積為j的背包的物品的最大//價值。[13]

（3）貪心演算法解決背包問題有幾種策略：

(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。

如圖1，大體上說明了動態規劃解決的0／1背包問題和貪心演算法解決的問題之間的區別，

圖1

（4）貪心演算法解決背包問題的演算法實現：

代碼如下：

#include<iostream.h>
structgoodinfo
{
floatp;//物品效益
floatw;//物品重量
floatX;//物品該放的數量
intflag;//物品編號
};//物品信息結構體
voidInsertionsort(goodinfogoods[],intn)
{//插入排序，按pi/wi價值收益進行排序，一般教材上按冒泡排序
intj,i;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].p>goods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}//按物品效益，重量比值做升序排列
voidbag(goodinfogoods[],floatM,intn)
{

floatcu;
inti,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M;//背包剩餘容量
for(i=1;i<n;i++)
{
if(goods[i].w>cu)//當該物品重量大與剩餘容量跳出
break;
goods[i].X=1;
cu=cu-goods[i].w;//確定背包新的剩餘容量
}
if(i<=n)
goods[i].X=cu/goods[i].w;//該物品所要放的量
/*按物品編號做降序排列*/
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].flag<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
///////////////////////////////////////////
cout<<"最優解為:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
voidmain()
{
cout<<"|--------運用貪心法解背包問題---------|"<<endl;
intj,n;floatM;
goodinfo*goods;//定義一個指針
while(j)
{
cout<<"請輸入物品的總數量：";
cin>>n;
goods=newstructgoodinfo[n+1];//
cout<<"請輸入背包的最大容量：";
cin>>M;
cout<<endl;
inti;
for(i=1;i<=n;i++)
{goods[i].flag=i;
cout<<"請輸入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"請輸入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
cout<<endl;

}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press<1>torunagian"<<endl;
cout<<"press<0>toexit"<<endl;
cin>>j;
}
}

Ⅳ 動態規劃

動態規劃

動態規劃（Dynamic Programming，簡稱DP）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式來求解復雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題。

優化目標：在背包容量受限的約束下，得到背包中的物品價值之和的最大值。

（1）01背包問題

• 題目背景：給定N種物品和容量為V的背包，每個物品由兩個屬性：體積v和價值w。每種物品最多隻能用一次，即每個物品的使用次數∈{0,1}。
• 分析：

  狀態定義：dp[i][j]表示前i個物品在背包容量為j時的最大價值。

  狀態轉移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])，其中v[i]表示第i個物品的體積，w[i]表示第i個物品的價值。

  初始條件：dp[0][j] = 0，表示沒有物品時背包的價值為0。

  優化：可以將二維數組降為一維，即dp[j] = max(dp[j], dp[j-v[i]] + w[i])，注意枚舉j時要從大到小，以避免重復使用同一物品。

（2）完全背包問題

• 題目背景：給定N種物品和容量為V的背包，每個物品由兩個屬性：體積v和價值w。每種物品可以用無限次。
• 分析：

  狀態定義與01背包相同。

  狀態轉移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])，注意這里dp[i][j-v[i]] + w[i]中的dp[i]表示當前物品i還可以繼續使用。

  優化：同樣可以將二維數組降為一維，枚舉j時從小到大即可。

（3）多重背包問題

• 題目背景：給定N種物品和容量為V的背包，每個物品由兩個屬性：體積v和價值w。每種物品的可用的次數不同，用S_i表示第i個物品最多可用的次數。
• 分析：

  可以將多重背包問題轉化為01背包問題，即將每種物品拆分成多個只能使用一次的物品。

  使用二進制優化，將每種物品的數量S_i拆分成logS_i個物品，然後對每個新的物品應用01背包的解法。

（4）分組背包問題

• 題目背景：物品有N組，每組有若干個物品，每組最多隻能選一個物品。
• 分析：

  狀態定義：dp[i][j]表示前i組物品在背包容量為j時的最大價值。

  狀態轉移方程：對於第i組物品，遍歷該組內的所有物品，選擇價值最大的那個物品進行狀態轉移。

遞推方程有明顯的線性關系。

（1）數字三角形

• 題目：給定一個數字三角形，從頂部走到底部，每一步只能走到下一行中相鄰的結點上，求路徑上數字之和的最大值。
• 分析：

  狀態定義：dp[i][j]表示走到第i行第j列時的最大路徑和。

  狀態轉移方程：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]，其中triangle[i][j]表示數字三角形中第i行第j列的數字。

（2）最長上升子序列

• 題目：給定一個無序的整數數組，找到其中最長上升子序列的長度。
• 分析：

  狀態定義：dp[i]表示以第i個元素結尾的最長上升子序列的長度。

  狀態轉移方程：dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]。

  優化：使用二分法優化查找過程，將時間復雜度降低到O(nlogn)。

（3）最長公共子序列

• 題目：給定兩個字元串text1和text2，求它們的最長公共子序列的長度。
• 分析：

  狀態定義：dp[i][j]表示text1的前i個字元和text2的前j個字元的最長公共子序列的長度。

  狀態轉移方程：dp[i][j] = dp[i-1][j-1] + 1，如果text1[i-1] == text2[j-1]；否則dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

（4）最短編輯距離

• 題目：給定兩個字元串word1和word2，求將它們變成相同字元串所需的最少編輯操作次數（包括插入一個字元、刪除一個字元或替換一個字元）。
• 分析：

  狀態定義：dp[i][j]表示word1的前i個字元和word2的前j個字元的最短編輯距離。

  狀態轉移方程：

  如果word1[i-1] == word2[j-1]，則dp[i][j] = dp[i-1][j-1]；

  否則dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])。

定義狀態表示時，定義了一個區間。

（1）石子合並

• 題目：給定一堆石子，每次只能合並相鄰的兩堆石子，合並後的石子重量為兩堆石子的重量和。求合並成一堆石子所需的最小代價（每次合並的代價為合並前兩堆石子的重量和）。
• 分析：

  狀態定義：dp[i][j]表示將第i堆到第j堆石子合並成一堆的最小代價。

  狀態轉移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])，其中i <= k < j，sum[j]表示前j堆石子的總重量。

（1）整數劃分

• 題目：給定一個正整數n，求將其拆分成若干個正整數之和的方案數。
• 分析：

  解法一（完全背包）：將整數n視為一個容量為n的背包，物品體積為1到n，求恰好裝滿背包的方案數。

  解法二（動態規劃）：dp[i][j]表示將整數i拆分成不大於j的正整數之和的方案數。狀態轉移方程為dp[i][j] = dp[i][j-1] + dp[i-j][j]（如果i >= j）。

（此處省略具體例子和分析，數位壓縮DP通常用於處理與數字位數相關的問題，通過壓縮狀態來減少空間復雜度。）

（此處省略具體例子和分析，狀態壓縮DP通常用於處理狀態數量較多但可以通過某種方式（如二進制）進行壓縮的問題。）

（此處省略具體例子和分析，樹形DP通常用於處理樹形結構上的問題，通過遞歸或迭代的方式在樹上進行動態規劃。）

記憶搜索是一種結合了深度優先搜索和動態規劃思想的演算法。它通過在搜索過程中記錄已經計算過的狀態，避免重復計算，從而提高效率。記憶搜索通常用於解決具有重疊子問題的問題。

以上是對動態規劃及其常用模型的詳細介紹。動態規劃是一種非常強大的演算法思想，廣泛應用於各種領域。在實際應用中，需要根據問題的具體特點選擇合適的動態規劃模型和狀態定義方式。

Ⅳ 分析用動態規劃和貪心演算法求解背包問題的差異

動態規劃本質是以空間換時間，算出了所有可行解的值域。

而貪心演算法，每次選則最優的，而結果未必最優。
舉個簡單例子。
背包能裝8kg,有3個物品，分別為3kg,4kg,5kg
動態規劃，是計算，3+4， 3+5，得出解，最大的是3+5=8kg
貪心演算法，是選擇，第一次選最大的：5kg<8kg，第二次選則剩下的最大的4kg，4+5>8,故而解為5kg。

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