devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法设计与分析-分支限界_分支限界题目

作者：木道寻08 | 2024-07-08 14:07:45

赞

踩

分支限界题目

问题A: 分支限界法-单源最短路径问题

题目描述

 已知一个加权有向图（为了计算方便，假设编号为1的顶点是入度为0的源点，编号为n的顶点是出度为0的汇点，图中的顶点从1开始编号），要求计算图中从源点出发到汇点的最短距离及其对应的路径（逆向输出）。

输入

第1行输入两个整数，分别表示图G中顶点数n和边数m。
第2 - m+1行每行输入三个整数，分别表示顶点i和顶点j的编号以及由这两个顶点的有向边上的权。

输出

第1行输出源点到汇点的最短路径距离。
第2行输出汇点到源点的逆向最短路径。

样例输入

 复制

5 7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
样例输出

 复制

60
5 3 4 1
提示
#include <stdio.h>

#define INFINITY  65535
#define MaxSize 100 //顺序队列最大长度 

int n;  //图中的顶点个数 
int m; //图中的边的个数 
int a[20][20];//邻接矩阵 
int label[20]; // 存储源点到其余顶点最短路径上的最后一个顶点编号，0号单元不用
int distance[20]; // 存储从源点出发到其余各个顶点的最短距离，0号单元不用 

void CreateGraph() {
	int i,j,u,v,w;

	for(i=1; i<=n; i++){ // 初始化邻接矩阵
		for(j=1; j<=n; j++) a[i][j] = INFINITY;
	}
	for(i=1; i<=m; i++) { // 输入边信息填写有向图的邻接矩阵
		scanf("%d %d %d",&u,&v,&w);  // 边的信息包括顶点1和顶点2的编号以及它们之间的距离
		a[u][v]=w;
	}
}

typedef struct {
	int length; // 存储源点到此顶点的当前距离 
	int i; //存储顶点在图中的编号 
} QNode; //存放解空间树中的结点数据

typedef struct { //存放结点的顺序循环队列
	QNode Q[MaxSize];
	int front,rear;
} SqQueue;

void InitQueue(SqQueue &sq) { //队列初始化
	sq.front=0;
	sq.rear=0;
}

int QueueEmpty(SqQueue sq) {	//判断队列是否为空
	if(sq.front==sq.rear) {
		return 1;
	} else {
		return 0;
	}
}

int QueueFull(SqQueue sq) { //判断队列是否为满
	if(sq.front==(sq.rear+1)%MaxSize) {
		return 1;
	} else {
		return 0;
	}
}

void EnQueue(SqQueue &sq, QNode e) { //入队
	if(!QueueFull(sq)) {
		sq.Q[sq.rear]=e;
		sq.rear=(sq.rear+1)%MaxSize;
	} else {
		printf("Error:queue is full\n");
	}
}

void DeQueue(SqQueue &sq, QNode &e) { //出队
	if(!QueueEmpty(sq)) {
		e=sq.Q[sq.front];
		sq.front=(sq.front+1)%MaxSize;
	} else {
		printf("Error:queue is empty\n");
	}
}

void BB() {//从顶点1开始 

        SqQueue sq;
	InitQueue(sq);
	
	QNode e;
	e.length=0;
	e.i=1; // 构造根结点
	EnQueue(sq,e);

	while(!QueueEmpty(sq)) {
		DeQueue(sq,e);
		int i=e.i;
		int length=e.length;
		for(int j=1;j<=n;j++){
			if(a[i][j]<INFINITY && length+a[i][j]<distance[j]){
				________________________
			}
		} 	
	}
}


int main(void) {

	scanf("%d %d",&n,&m);

	CreateGraph();
	
	for(int i=1; i<=n; i++){ // 初始化源点到各个顶点的距离 
    	distance[i]=INFINITY;
	}
	distance[1]=0; // 源点编号为1 
    label[1]=0; // 表示1号顶点没有前驱结点 

	BB();

	printf("%d\n",distance[n]);
	
	for(int u=n; u!=0; u=label[u]) printf("%d ",u);

	return 0;
}
  1. #include <stdio.h>
  2.  
  3. #define INFINITY  65535
  4. #define MaxSize 100 //顺序队列最大长度 
  5.  
  6. int n;  //图中的顶点个数 
  7. int m; //图中的边的个数 
  8. int a[20][20];//邻接矩阵 
  9. int label[20]; // 存储源点到其余顶点最短路径上的最后一个顶点编号，0号单元不用
  10. int distance[20]; // 存储从源点出发到其余各个顶点的最短距离，0号单元不用 
  11.  
  12. void CreateGraph() {
  13. 	int i,j,u,v,w;
  14.  
  15. 	for(i=1; i<=n; i++){ // 初始化邻接矩阵
  16. 		for(j=1; j<=n; j++) a[i][j] = INFINITY;
  17. 	}
  18. 	for(i=1; i<=m; i++) { // 输入边信息填写有向图的邻接矩阵
  19. 		scanf("%d %d %d",&u,&v,&w);  // 边的信息包括顶点1和顶点2的编号以及它们之间的距离
  20. 		a[u][v]=w;
  21. 	}
  22. }
  23.  
  24. typedef struct {
  25. 	int length; // 存储源点到此顶点的当前距离 
  26. 	int i; //存储顶点在图中的编号 
  27. } QNode; //存放解空间树中的结点数据
  28.  
  29. typedef struct { //存放结点的顺序循环队列
  30. 	QNode Q[MaxSize];
  31. 	int front,rear;
  32. } SqQueue;
  33.  
  34. void InitQueue(SqQueue &sq) { //队列初始化
  35. 	sq.front=0;
  36. 	sq.rear=0;
  37. }
  38.  
  39. int QueueEmpty(SqQueue sq) {	//判断队列是否为空
  40. 	if(sq.front==sq.rear) {
  41. 		return 1;
  42. 	} else {
  43. 		return 0;
  44. 	}
  45. }
  46.  
  47. int QueueFull(SqQueue sq) { //判断队列是否为满
  48. 	if(sq.front==(sq.rear+1)%MaxSize) {
  49. 		return 1;
  50. 	} else {
  51. 		return 0;
  52. 	}
  53. }
  54.  
  55. void EnQueue(SqQueue &sq, QNode e) { //入队
  56. 	if(!QueueFull(sq)) {
  57. 		sq.Q[sq.rear]=e;
  58. 		sq.rear=(sq.rear+1)%MaxSize;
  59. 	} else {
  60. 		printf("Error:queue is full\n");
  61. 	}
  62. }
  63.  
  64. void DeQueue(SqQueue &sq, QNode &e) { //出队
  65. 	if(!QueueEmpty(sq)) {
  66. 		e=sq.Q[sq.front];
  67. 		sq.front=(sq.front+1)%MaxSize;
  68. 	} else {
  69. 		printf("Error:queue is empty\n");
  70. 	}
  71. }
  72.  
  73. void BB() {//从顶点1开始 
  74.  
  75.         SqQueue sq;
  76. 	InitQueue(sq);
  77. 	
  78. 	QNode e;
  79. 	e.length=0;
  80. 	e.i=1; // 构造根结点
  81. 	EnQueue(sq,e);
  82.  
  83. 	while(!QueueEmpty(sq)) {
  84. 		DeQueue(sq,e);
  85. 		int i=e.i;
  86. 		int length=e.length;
  87. 		for(int j=1;j<=n;j++){
  88. 			if(a[i][j]<INFINITY && length+a[i][j]<distance[j]){
  89. 				distance[j]=length+a[i][j];
  90. 				label[j]=i;
  91. 				e.length=distance[j];
  92. 				e.i=j;
  93. 				EnQueue(sq,e);
  94. 			}
  95. 		} 	
  96. 	}
  97. }
  98.  
  99.  
  100. int main(void) {
  101.  
  102. 	scanf("%d %d",&n,&m);
  103.  
  104. 	CreateGraph();
  105. 	
  106. 	for(int i=1; i<=n; i++){ // 初始化源点到各个顶点的距离 
  107.     	distance[i]=INFINITY;
  108. 	}
  109. 	distance[1]=0; // 源点编号为1 
  110.     label[1]=0; // 表示1号顶点没有前驱结点 
  111.  
  112. 	BB();
  113.  
  114. 	printf("%d\n",distance[n]);
  115. 	
  116. 	for(int u=n; u!=0; u=label[u]) printf("%d ",u);
  117.  
  118. 	return 0;
  119. }

问题B: 分支限界法-0-1背包问题

题目描述

给定n种物品和一背包。物品i (1≤i≤n) 的重量是wi (wi > 0)，其价值为vi (vi > 0)，背包的容量为c (c > 0)。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 

输入

第1行输入两个整数分别表示物品的数量和背包容量。
第2行输入n个整数分别表示每个物品的重量。
第3行输入n个整数分别表示每个物品的获利。

输出

第1行输出整个背包的最大获利。

样例输入

 复制

3 50
45 25 25
28 15 15
样例输出

 复制

30
提示
 

 

#include <stdio.h> // 为了方便编写限界函数，假设按照单位重量获利递增的顺序输入每个物品的重量和获利。 #define MaxSize 100 //最多节点数 int n; //物品数量 int c; //背包容量 int w[MaxSize]; //依次存放各个物品的重量，0号单元不用 int v[MaxSize]; //依次存放各个物品的价值，0号单元不用 int bestx[MaxSize]; //存放程序执行过程中已经找到的当前最优解，0号单元不用 int bestv=0; //存放程序执行过程中已经找到的当前最优值 typedef struct { int cw; // 当前已放物品的重量 int cv; // 当前已放物品的获利 int i; //当前在解空间树中的层数，假设根结点是第1层 int x[MaxSize]; // 当前解向量 } QNode; //存放解空间树中的节点数据 typedef struct { //存放节点的顺序循环队列 QNode Q[MaxSize]; int front,rear; } SqQueue; void InitQueue(SqQueue &sq) { //队列初始化 sq.front=0; sq.rear=0; } int QueueEmpty(SqQueue sq) { //判断队列是否为空 if(sq.front==sq.rear) { return 1; } else { return 0; } } int QueueFull(SqQueue sq) { //判断队列是否为满 if(sq.front==(sq.rear+1)%MaxSize) { return 1; } else { return 0; } } void EnQueue(SqQueue &sq, QNode e) { //入队 if(!QueueFull(sq)) { sq.Q[sq.rear]=e; sq.rear=(sq.rear+1)%MaxSize; } else { printf("Error:queue is full\n"); } } void DeQueue(SqQueue &sq, QNode &e) { //出队 if(!QueueEmpty(sq)) { e=sq.Q[sq.front]; sq.front=(sq.front+1)%MaxSize; } else { printf("Error:queue is empty\n"); } } void BB() { SqQueue sq; InitQueue(sq); // 构造根结点 QNode e; e.cw=0; e.cv=0; e.i=1; EnQueue(sq,e); while(!QueueEmpty(sq)) { DeQueue(sq,e); if(e.i==n+1) {// 处理解空间树中的叶子结点 if(e.cv>=bestv){ bestv=e.cv; for(int j=1; j<=n; j++) { bestx[j]=e.x[j]; } } } else { // 处理解空间树中的非叶子结点 //处理左孩子，要该物品 QNode le=e; ___________ le.i++; // 准备好进入下一层 if(le.cw<=c) { // 如果满足约束条件 EnQueue(sq,le); } //处理右孩子，不要该物品 QNode re=e; _____________ re.i++; // 准备好进入下一层 EnQueue(sq,re); } } } int main(void) { scanf("%d %d",&n,&c); for(int i=1; i<=n; i++) { scanf("%d",&w[i]); } for(int i=1; i<=n; i++) { scanf("%d",&v[i]); } BB(); printf("%d\n",bestv); return 0; }
 

  1. #include <stdio.h>
  2.  
  3. // 为了方便编写限界函数，假设按照单位重量获利递增的顺序输入每个物品的重量和获利。
  4.  
  5. #define MaxSize 100	//最多节点数
  6.  
  7. int n; //物品数量
  8. int c; //背包容量
  9.  
  10. int w[MaxSize];	//依次存放各个物品的重量，0号单元不用 
  11. int v[MaxSize];	//依次存放各个物品的价值，0号单元不用
  12. int bestx[MaxSize];	//存放程序执行过程中已经找到的当前最优解，0号单元不用
  13. int bestv=0; //存放程序执行过程中已经找到的当前最优值
  14.  
  15. typedef struct {
  16. 	int cw; // 当前已放物品的重量
  17. 	int cv; // 当前已放物品的获利
  18. 	int i; //当前在解空间树中的层数，假设根结点是第1层
  19. 	int x[MaxSize]; // 当前解向量
  20. } QNode; //存放解空间树中的节点数据
  21.  
  22. typedef struct { //存放节点的顺序循环队列
  23. 	QNode Q[MaxSize];
  24. 	int front,rear;
  25. } SqQueue;
  26.  
  27. void InitQueue(SqQueue &sq) { //队列初始化
  28. 	sq.front=0;
  29. 	sq.rear=0;
  30. }
  31.  
  32. int QueueEmpty(SqQueue sq) { //判断队列是否为空
  33. 	if(sq.front==sq.rear) {
  34. 		return 1;
  35. 	} else {
  36. 		return 0;
  37. 	}
  38. }
  39.  
  40. int QueueFull(SqQueue sq) { //判断队列是否为满
  41. 	if(sq.front==(sq.rear+1)%MaxSize) {
  42. 		return 1;
  43. 	} else {
  44. 		return 0;
  45. 	}
  46. }
  47.  
  48. void EnQueue(SqQueue &sq, QNode e) { //入队
  49. 	if(!QueueFull(sq)) {
  50. 		sq.Q[sq.rear]=e;
  51. 		sq.rear=(sq.rear+1)%MaxSize;
  52. 	} else {
  53. 		printf("Error:queue is full\n");
  54. 	}
  55. }
  56.  
  57. void DeQueue(SqQueue &sq, QNode &e) { //出队
  58. 	if(!QueueEmpty(sq)) {
  59. 		e=sq.Q[sq.front];
  60. 		sq.front=(sq.front+1)%MaxSize;
  61. 	} else {
  62. 		printf("Error:queue is empty\n");
  63. 	}
  64. }
  65.  
  66. void BB() {
  67.  
  68. 	SqQueue sq;
  69. 	InitQueue(sq);
  70.  
  71. 	// 构造根结点
  72. 	QNode e;
  73. 	e.cw=0;
  74. 	e.cv=0;
  75. 	e.i=1;
  76. 	EnQueue(sq,e);
  77.  
  78. 	while(!QueueEmpty(sq)) {
  79.  
  80. 		DeQueue(sq,e);
  81.  
  82. 		if(e.i==n+1) {// 处理解空间树中的叶子结点
  83. 			if(e.cv>=bestv){
  84. 				bestv=e.cv;
  85. 				for(int j=1; j<=n; j++) {
  86. 					bestx[j]=e.x[j];
  87. 				}
  88. 			}	
  89. 		} else { // 处理解空间树中的非叶子结点
  90. 			//处理左孩子，要该物品
  91. 			QNode le = e;  
  92.             le.x[e.i] = 1; // 选择当前物品  
  93.             le.cw += w[e.i]; // 更新当前重量  
  94.             le.cv += v[e.i]; // 更新当前价值  
  95.             le.i++; // 准备好进入下一层  
  96.             if (le.cw <= c) { // 如果满足约束条件  
  97.                 EnQueue(sq, le);  
  98.             }  
  99.             // 处理右孩子，不要该物品  
  100.             QNode re = e;  
  101.             // re.x[e.i] 已经是0，因为是从e复制过来的  
  102.             re.i++; // 准备好进入下一层  
  103.             EnQueue(sq, re);  
  104. 		}
  105. 	}
  106. }
  107.  
  108. int main(void) {
  109.  
  110. 	scanf("%d %d",&n,&c);
  111.  
  112. 	for(int i=1; i<=n; i++) {
  113. 		scanf("%d",&w[i]);
  114. 	}
  115.  
  116. 	for(int i=1; i<=n; i++) {
  117. 		scanf("%d",&v[i]);
  118. 	}
  119.  
  120. 	BB();
  121.  
  122. 	printf("%d\n",bestv);
  123.  
  124. 	return 0;
  125. }
 


                

        声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号