■回溯法
0-1背包问题是回溯法中的子集选取问题，0-1背包问题的解空间可以用子集树来表示。
设cw为当前重量，w[]为每个物品的重量。在搜索解空间树时，只要其左儿子结点是一个可行结点，即当前重量加该结点的重量小于等于背包容量(cw+w[i]<=c)，搜索就进入其左子树。
设上界函数为Bound(int i)，当前最优值为bestp。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。右子树中有可能包含最优解的条件是右子树的上界大于当前最优值(Bound(i+1)
>bestp)。
计算右子树上界的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下去时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。排序用到的算法是哨兵算法。
本程序将可选物品定义为一个表来进行运算，比定义数组简洁。
typedef struct{
double p;//物品价值
double w;//物品重量
double v;//物品单位价值
int flag;//物品排序前的位置
}RedType;
typedef struct{
int length;
RedType r[5001];
}SqList;
伪代码如下：
int n;//物品数量
double c;//背包容量
int x[5001]={0};//物品是否放入标志
double bestp=0;//当前最优价值
double cp=0;//当前价值
double cw=0;//当前重量
void sort()
{
…/*利用哨兵法，将物品按单位价值L.r[i].v排序*/
}
int Bound(int i)/*上界函数*/
{
int cleft=c-cw;/*剩余容量*/
while(i<=n&&L.r[i].w<=cleft)/*以物品单位价值递减序装入物品*/
{
cleft-=L.r[i].w;
i++;
}
…/*将背包完全满*/
return;/*返回上界*/
}
void Backtrack(int i)//回溯函数
{
if(i>n)/*到达叶子结点*/
{
bestp=cp;
return;
}
if(cw+L.r[i].w<=c)/*进入左子树*/
{
cw+=L.r[i].w;
cp+=L.r[i].p;
x[i]=1;/*将标记x记为1*/
Backtrack(i+1);
cw-=L.r[i].w;
cp-=L.r[i].p;
}
if(Bound(i+1)>bestp)/*进入右子树*/
Backtrack(i+1);
}
int main()
{
… /*输入数据*/
sort();/*对输入的数据按物品单位价值排序*/
Backtrack(1);/*从第一层开始搜索*/
for(i=1;i<=n;i++) /*输出结果*/
for(j=1;j<=n;j++)
if(L.r[j].flag == i)
{
printf(“%d %d\n”,i,x[j]);
break;
}
printf(“%g\n”,bestp);
}
主程序在输入数据后，调用sort()函数对输入的数据按物品单位价值排序，再调用Backtrack(1)函数从第一层开始递归搜索，最后输入数据。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176540.html原文链接：https://javaforall.net
