回溯算法---01背包问题

背包问题：

给定n种物品（每种物品仅有一件）和一个背包。物品i的重量是wi ，其价值为pi ，背包的容量为w。问应如何选择物品装入背包，使得装入背包中的物品的总价值最大？

l 如果在装入背包时，物品可以切割，即可以只装入一部分，这种情况下的问题称为背包问题。

l 在装入背包时，每种物品i只有两种选择，装入或者不装入，既不能装入多次，也不能只装入一部分。因此，此问题称为0-1背包问题。

要想得到最优解，就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说，总应该把那些单位效益最高的物体先放入背包。

背包问题可看做是一种回溯：

每个包是一个节点， 节点共有2个候选值0、1 。 0代表不放人背包中， 1代表放入背包中。

因此，背包问题就转换为找到满足条件的路径问题。

因此，可用回溯方法解决。

回溯方法解决背包问题：

方法一：

// 判断节点（I,j）是否为解路径上的节点,其中：

//

// i表示解路径上的第i个测试节点、j表示该节点的某个候选值

// A[i] 保存第i个节点选用的值

BOOL TestNode(I ,j)

{

更新相关参数值（假定选择了此候选值j，因此更新受影响的参数值）；

与0—(i-1) 层进行判断，看是否与以遍历的节点有冲突

若有冲突， 则返回FALSE；

若无冲突， 则 将节点i的值j,保存到对应的数组中A[I]=J;

判断I是否为最后一层,

若是最后一层，则成功找到一条解路径，返回TRUE；

若不是最后一层，则判断第i+1层是否有正确的节点。

BOOL bFlag=FALSE;

FOR(k=0;k< CANDIDATA_NUM;k++) //候选值【0，。。。，CANDIDATA_NUM -1】

{

If(TestNode(i+1,k))

{

找到一个解；

bFlag=True;

}

//不管TestNode(i+1,k)是成功的还是失败的，退出后，都要对参数进行还原

还原相关参数值（撤销了候选值k，因此要还原受影响的参数值）；

}

RETURN bFlag;

}

int m,n=5,x[10]={0};int w[6]={0,2,2,6,5,5},v[6]={0,6,3,5,4,6};int c=10;int cw=0,cv=0,bestv=0;int ok(int k){int u=1;if(cw>c)u=0;return u;}int f(int k){int i;if (k>n){for(i=1;i<=n;i++)printf("%d",x[i]);if(cv>bestv)bestv=cv;printf("\n");}else{x[k]=1;    //判断候选值1cw+=w[k];cv+=v[k];if(ok(k))f(k+1);cw-=w[k];  //判断候选值0cv-=v[k];x[k]=0;  if(ok(k))f(k+1);}return k;}