1、問題描述：
給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問:應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
形式化描述：給定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi達最大.即一個特殊的整數規劃問題。
2、最優性原理：
設(y1,y2,…,yn)是 (3.4.1)的一個最優解.則(y2,…,yn)是下面相應子問題的一個最優解:
證明:使用反證法。若不然,設(z2,z3,…,zn)是上述子問題的一個最優解,而(y2,y3,…,yn)不是它的最優解。顯然有
∑vizi > ∑viyi (i=2,…,n)
且 w1y1+ ∑wizi<= c
因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)
說明(y1,z2, z3,…,zn)是(3.4.1)0-1背包問題的一個更優解,導出(y1,y2,…,yn)不是背包問題的最優解,矛盾。
3、遞推關系：
設所給0-1背包問題的子問題
的最優值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優值。由0-1背包問題的最優子結構性質，可以建立計算m(i，j)的遞歸式:
注:(3.4.3)式此時背包容量為j，可選擇物品為i。此時在對xi作出決策之後,問題處於兩種狀態之一:
(1)背包剩余容量是j,沒產生任何效益；
(2)剩余容量j-wi,效益值增長了vi ；
算法具體代碼如下：
[cpp]
//3d10-1 動態規劃 背包問題
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N = 4;
void Knapsack(int v[],int w[],int c,int n,int m[][10]);
void Traceback(int m[][10],int w[],int c,int n,int x[]);
int main()
{
int c=8;
int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下標從1開始
int x[N+1];
int m[10][10];
cout<<"待裝物品重量分別為："<<endl;
for(int i=1; i<=N; i++)
{
cout<<w[i]<<" ";
}
cout<<endl;
cout<<"待裝物品價值分別為："<<endl;
for(int i=1; i<=N; i++)
{
cout<<v[i]<<" ";
}
cout<<endl;
Knapsack(v,w,c,N,m);
cout<<"背包能裝的最大價值為："<<m[1][c]<<endl;
Traceback(m,w,c,N,x);
cout<<"背包裝下的物品編號為："<<endl;
for(int i=1; i<=N; i++)
{
if(x[i]==1)
{
cout<<i<<" ";
}
}
cout<<endl;
return 0;
}
void Knapsack(int v[],int w[],int c,int n,int m[][10])
{
int jMax = min(w[n]-1,c);//背包剩余容量上限 范圍[0~w[n]-1]
for(int j=0; j<=jMax;j++)
{
m[n][j]=0;
}
for(int j=w[n]; j<=c; j++)//限制范圍[w[n]~c]
{
m[n][j] = v[n];
}
for(int i=n-1; i>1; i--)
{
jMax = min(w[i]-1,c);
for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c
{
m[i][j] = m[i+1][j];//沒產生任何效益
}
for(int j=w[i]; j<=c; j++) //背包不同剩余容量j-wi >c
{
m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增長vi
}
}
m[1][c] = m[2][c];
if(c>=w[1])
{
m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}
}
//x[]數組存儲對應物品0-1向量,0不裝入背包，1表示裝入背包
void Traceback(int m[][10],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;
}
算法執行過程對m[][]填表及Traceback回溯過程如圖所示：
從m(i，j)的遞歸式容易看出，算法Knapsack需要O(nc)計算時間; Traceback需O(n)計算時間；算法總體需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c>2^n時，算法需要Ω(n2^n)計算時間。
4、算法的改進：
由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1≤i≤n)，函數m(i,j)是關於變量j的階梯狀單調不減函數。跳躍點是這一類函數的描述特征。在一般情況下，函數m(i,j)由其全部跳躍點唯一確定。如圖所示。
對每一個確定的i(1≤i≤n)，用一個表p[i]存儲函數m(i，j)的全部跳躍點。表p[i]可依計算m(i，j)的遞歸式遞歸地由表p[i+1]計算，初始時p[n+1]={(0，0)}。
一個例子：n=3，c=6，w={4，3，2}，v={5，2，1}。
函數m(i,j)是由函數m(i+1,j)與函數m(i+1,j-wi)+vi作max運算得到的。因此，函數m(i,j)的全部跳躍點包含於函數m(i+1，j)的跳躍點集p[i+1]與函數m(i+1，j-wi)+vi的跳躍點集q[i+1]的並集中。易知，(s,t)∈q[i+1]當且僅當wi<=s<=c且(s-wi,t-vi)∈p[i+1]。因此，容易由p[i+1]確定跳躍點集q[i+1]如下：
q[i+1]=p[i+1]⊕(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))∈p[i+1]}
另一方面，設(a，b)和(c，d)是p[i+1]∪q[i+1]中的2個跳躍點，則當c>=a且d<b時，(c，d)受控於(a，b)，從而(c，d)不是p[i]中的跳躍點。除受控跳躍點外，p[i+1]∪q[i+1]中的其他跳躍點均為p[i]中的跳躍點。
由此可見，在遞歸地由表p[i+1]計算表p[i]時，可先由p[i+1]計算出q[i+1]，然後合並表p[i+1]和表q[i+1]，並清除其中的受控跳躍點得到表p[i]。
例：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。跳躍點的計算過程如下：
初始時p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]⊕(w5,v5)={(4,6)}。 p[5]={(0,0),(4,6)}。q[5]=p[5]⊕(w4,v4)={(5,4),(9,10)}。從跳躍點集p[5]與q[5]的並集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(5,4)受控於跳躍點(4,6)。將受控跳躍點(5,4)清除後，得到
p[4]={(0,0),(4,6),(9,10)}
q[4]=p[4]⊕(6，5)={(6，5)，(10，11)}
p[3]={(0，0)，(4，6)，(9，10)，(10，11)}
q[3]=p[3]⊕(2，3)={(2，3)，(6，9)}
p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}
q[2]=p[2]⊕(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}
p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}
p[1]的最後的那個跳躍點(8,15)給出所求的最優值為m(1,c)=15。
具體代碼實現如下：
[cpp]
//3d10-2 動態規劃 背包問題 跳躍點優化
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N = 4;
template<class Type>
int Knapsack(int n,Type c,Type v[],Type w[],int **p,int x[]);
template<class Type>
void Traceback(int n,Type w[],Type v[],Type **p,int *head,int x[]);
int main()
{
int c=8;
int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下標從1開始
int x[N+1];
int **p = new int *[50];
for(int i=0;i<50;i++)
{
p[i] = new int[2];
}
cout<<"待裝物品重量分別為："<<endl;
for(int i=1; i<=N; i++)
{
cout<<w[i]<<" ";
}
cout<<endl;
cout<<"待裝物品價值分別為："<<endl;
for(int i=1; i<=N; i++)
{
cout<<v[i]<<" ";
}
cout<<endl;
cout<<"背包能裝的最大價值為："<<Knapsack(N,c,v,w,p,x)<<endl;
cout<<"背包裝下的物品編號為："<<endl;
for(int i=1; i<=N; i++)
{
if(x[i]==1)
{
cout<<i<<" ";
}
}
cout<<endl;
for(int i=0;i<50;i++)
{
delete p[i];
}
delete[] p;
return 0;
}
template<class Type>
int Knapsack(int n,Type c,Type v[],Type w[],int **p,int x[])
{
int *head = new int[n+2];
head[n+1]=0;
p[0][0]=0;//p[][0]存儲物品重量
p[0][1]=0;//p[][1]存儲物品價值，物品n的跳躍點（0，0）
// left 指向p[i+1]的第一個跳躍點，right指向最後一個
//拿書上的例子來說，若計算p[3]=0;則left指向p[4]的第一跳躍點（0 0）right指向（9,10）
int left = 0,right = 0,next = 1;//next即下一個跳躍點要存放的位置
head[n]=1;//head[n]用來指向第n個物品第一個跳躍點的位置
for(int i=n; i>=1; i--)
{
int k = left;//k指向p[ ]中跳躍點,移動k來判斷p[]與p[]+（w v）中的受控點
for(int j=left; j<=right; j++)
{
if(p[j][0]+w[i]>c) break;//剩余的空間不能再裝入i，退出for循環;
Type y = p[j][0] + w[i],m = p[j][1] + v[i];//計算p[ ]+（w v）
//若p[k][0]較小則(p[k][0] p[k][1])一定不是受控點，將其作為p[i]的跳躍點存儲
while(k<=right && p[k][0]<y)
{
p[next][0]=p[k][0];
p[next++][1]=p[k++][1];
}
//如果 p[k][0]==y而m<p[k][1]，則（y m）為受控點不存
if(k<=right && p[k][0]==y)
{
if(m<p[k][1])//對（p[k][0] p[k][1]）進行判斷
{
m=p[k][1];
}
k++;
}
// 若p[k][0]>=y且m> =p[k][1],判斷是不是當前i的最後一個跳躍點的受控點
//若不是則為i的跳躍點存儲
if(m>p[next-1][1])
{
p[next][0]=y;
p[next++][1]=m;
}
//若是，則對下一個元素進行判斷。
while(k<=right && p[k][1]<=p[next-1][1])
{
k++;
}
}
while(k<=right)
{
p[next][0]=p[k][0];
p[next++][1]=p[k++][1];//將i+1剩下的跳躍點作為做為i的跳躍點存儲
}
left = right + 1;
right = next - 1;
// 第i-1個物品第一個跳躍點的位置 head[0]指第0個物品第一個跳躍點的位置
head[i-1] = next;
}
Traceback(n,w,v,p,head,x);
return p[next-1][1];
}
//x[]數組存儲對應物品0-1向量,0不裝入背包，1表示裝入背包
template<class Type>
void Traceback(int n,Type w[],Type v[],Type **p,int *head,int x[])
{
//初始化j,m為最後一個跳躍點對應的第0列及第1列
//如上例求出的 最後一個跳躍點為（8 15）j=8,m=15
Type j = p[head[0]-1][0],m=p[head[0]-1][1];
for(int i=1; i<=n; i++)
{
x[i]=0;// 初始化數組；
for(int k=head[i+1]; k<=head[i]-1;k++)// 初始k指向p[2]的第一個跳躍點（0 0）
{
//判斷物品i是否裝入，如上例與跳躍點(6 9)相加等於（8 15）所以1裝入
if(p[k][0]+w[i]==j && p[k][1]+v[i]==m)
{
x[i]=1;//物品i被裝入，則x[i]置1
j=p[k][0];// j和m值置為滿足if條件的跳躍點對應的值
m=p[k][1];// 如上例j=6,m=9
break;//再接著判斷下一個物品
}
}
}
}
上述算法的主要計算量在於計算跳躍點集p[i](1≤i≤n)。由於q[i+1]=p[i+1]⊕(wi，vi)，故計算q[i+1]需要O(|p[i+1]|)計算時間。合並p[i+1]和q[i+1]並清除受控跳躍點也需要O(|p[i+1]|)計算時間。從跳躍點集p[i]的定義可以看出，p[i]中的跳躍點相應於xi,…,xn的0/1賦值。因此，p[i]中跳躍點個數不超過2^(n-i+1)。由此可見，算法計算跳躍點集p[i]所花費的計算時間為從而，改進後算法的計算時間復雜性為O(2^n)。當所給物品的重量wi(1≤i≤n)是整數時，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進後算法的計算時間復雜性為O(min{nc,2^n})。
運行結果如圖：
