n???wkxk?j?k?i??xk?{0,1},i?k?n

因若不然，设(z2，z3?zn)是上述问题的一个最优解，而(y2，y3?yn)不是它的最优解，由此可见??i?2nnn?vyii?2ni,且w1y1??wizi?c。因此

i?2n v1y1? ?vizi??viyi

i?2i?1nw1y1??wizi?c

i?2这说明(y1，z2?zn)是所给0-1背包问题的一个更优解，从而(y1，y2?yn)不是所给0-1背包问题的最优解。此为矛盾[1]。

② 递归关系

设所给0-1背包问题的子问题

max?vkxkk?in

n???wkxk?j?k?i ??xk?{0,1},i?k?n 的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i，i+1，??，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：

m(i?1),j),m(i?1,j?wi)?vi},j?wi?max{m(i,j)??

m(i?1,j),0?j?wj??vnj?wnm(n,j)??

?0?j?wn③ 算法描述

基于以上讨论，当wi(1?i?n)为正整数时，用二维数组m[][]来存储m(i,j)的相应值，可设计解0-1背包问题的动态规划算法Knapsack入下：

6

template

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 (int j=w[n];j<=c;j++)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++)m[i][j]=m[i+1][j];

for(intj=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

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; }[1]

7

④ 计算复杂性分析

利用动态规划求解0-1背包问题的复杂度为0(min{nc,2n}。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题[8]。

2.2 0-1背包问题在回溯法中的实现

2.2.1回溯法的基本原理与分析

回溯是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。

使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解的总组合数有2n个，因此随着物件数n的增大，其解的空间将以n2n级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。

下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结点进行搜索，利用限界函数避免移动到不可能产生解的子空间。 2.2.2 0-1背包问题的实现

① 回溯法的算法描述

回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。

左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到cp (当前节点所获收益)之上，若( r+cp)

8

?bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量， 当遇到第一个不能全部放人背包的对象时， 就使用它的一部分。

② 解0-1背包问题的回溯算法描述如下： template class Knap{

friend Typep Knapsack(Typep*,Typew*,Typew,int); private：

Typep Bound(int i); void Backtrack(int i); Typew c; //背包容量 int n; //物品数 Typew*w; //物品重量数组 Typep*p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最优价值 };

template

void knap::Backtrack(int i) {

if(i>n){//到达叶结点 bestp=cp; return;}

if(cw+w[i]<=c){//进入左子数 cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i];

if(Bound(i+1)>bestp) //进入右子数 Backtrack(i+1);

9