文档介绍：实验四回溯算法和分支限界法
基本题一：符号三角形问题
一、实验目的与要求
1、掌握符号三角形问题的算法；
2、初步掌握回溯算法；
二、实验题图
下面都是下图是由14个"+"和14个组成的符号三角形。2个同号下面都是“ +
cw+=w[i]*x[i];
cp+=P【i]*x[i]；
Backtrack(i+ l,cp,cw);
cw-=w[i]*x[i];
cp-=p[i]*x[i];
}
}
} int main()
inti;
bestp=O;
printf(”请输入背包最大容量:\n”)； scanf(”％d”,&c);
printf(”请输入物品个数:\n”)；
scanf("%d",&n);
printf(”请依次输入物品的重量:\n”)；
for(i=l;i<=n;i++)
scanf(”％d”,&w[i]);
printf(”请依次输入物品的价值:\n”)；
for(i= 1 ;iv=n;i++)
scanf("%d",&p[i]);
Backtrack( 1,0,0);
printf(”最大价值为:\n”)；
printf("%d\n" ,bestp);
printf(”被选中的物品依次是(0表示未选中，1表示选中)\n”);
for(i=l ;i<=n;i++)
printf("%d ",bestx[i]);
printf(”\n”)；
运行结果：
也・I:\计算机算法分析\0-l背包问题\Debug\0-l背包问题....6 I回
return 0;
请输入背包最大容量：
100
请输入物品个数：
3
请依次输入物品的重量：
50
70
40
请依次输入物品的价值：
4
8
3
最大价值为：
8
“被选中的物品依次是E表示未选中，1表示选中〉
^0 10
Press any key to continue.
分析：计算上界需要O(n)时间，在最坏情况下有0(25)个右儿子节点需要计算上界，故解0-1背包问题的回溯算法所需要的计算时间为O(n2An)。
提高题一：旅行商售货员问题的分支限界算法
一、实验目的与要求
1、掌握旅行商售货员问题的分支限界算法；
2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。
二、实验题：
某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（或总旅费）最小。
三、实验代码
^include <stdio. h>
^include <istream>
using namespace std;
// 宏定义
^define MAX_CITY_NUMBER 10 //城市最大数目
^define MAX_C0ST 10000000 //两个城市之间费用的最大值
// 全局变量
int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];
〃表示城市间边权重的数组
int City_Size; //表示实际输入的城市数目
int Best_Cost; //最小费用
int Best_Cost_Path[MAX_CITY_NUMBER];
〃最小费用时的路径
// 定义结点
typedef
struct Node(
int
Icost;
〃优先级
int
cc;
〃当前费用
int
rcost;
〃剩余所有结点的最小出边费用的和
int
s；
〃当前结点的深度，也就是它在解数组中的索引位置
int
x[MAX_CITY_NUMBER];
〃当前结点对应的路径
struct Node* pNext;
〃指向下一个结点
)Node;
// 定义堆和相关对操作
typedef struct MiniHeap(
Node* pHead; //堆的头
}MiniHeap;
//初始化
void InitMiniHeap(MiniHeap* pMiniHeap){
pMi n i Heap->pHead 二 new Node;
pMiniHeap->pHead->pNext = NULL;
}
〃入堆
void put(MiniHeap* pMiniHeap, Node node)(
Node* next;
Node* pre;
Node* pinnode二new Node; //将传进来的结点信息copy 一份保存
〃这样在函数外部对node的修改就不会影响到堆了
pinnode-〉cc = node, cc;