算法设计与分析-分支限界

2024-06-06 05:36

本文主要是介绍算法设计与分析-分支限界,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题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;
}
#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]){distance[j]=length+a[i][j];label[j]=i;e.length=distance[j];e.i=j;EnQueue(sq,e);}} 	}
}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;
}

问题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; }
#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.x[e.i] = 1; // 选择当前物品  le.cw += w[e.i]; // 更新当前重量  le.cv += v[e.i]; // 更新当前价值  le.i++; // 准备好进入下一层  if (le.cw <= c) { // 如果满足约束条件  EnQueue(sq, le);  }  // 处理右孩子,不要该物品  QNode re = e;  // re.x[e.i] 已经是0,因为是从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;
}

这篇关于算法设计与分析-分支限界的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1035233

相关文章

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景