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

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。
                            
                        

                    

                    
                    

                        
                            
                        
                    

                

                

                    相关文章
                

                    

                        

                            

                                

                                    
                                        不懂推荐算法也能设计推荐系统
                                    
                                

                            

                            

                                

                                    不懂推荐算法也能设计推荐系统
                                

                                

                                    本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。   相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        康拓展开（hash算法中会用到）
                                    
                                

                            

                            

                                

                                    康拓展开（hash算法中会用到）
                                

                                

                                    康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应）   公式：  X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!  其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）；  典型应用：  计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        性能分析之MySQL索引实战案例
                                    
                                

                            

                            

                                

                                    性能分析之MySQL索引实战案例
                                

                                

                                    文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结   一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        csu 1446 Problem  J Modified LCS （扩展欧几里得算法的简单应用）
                                    
                                

                            

                            

                                

                                    csu 1446 Problem  J Modified LCS （扩展欧几里得算法的简单应用）
                                

                                

                                    这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉  这也是自己独自做扩展欧几里得算法的题目  题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解  下面介绍一下exgcd的一些知识点：求ax + by = c的解  一、首先求ax + by = gcd(a,b)的解 这个
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势
                                    
                                

                            

                            

                                

                                    综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势
                                

                                

                                    LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。  优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        【数据结构】——原来排序算法搞懂这些就行，轻松拿捏
                                    
                                

                            

                            

                                

                                    【数据结构】——原来排序算法搞懂这些就行，轻松拿捏
                                

                                

                                    前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值  基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)
                                    
                                

                            

                            

                                

                                    poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)
                                

                                

                                    求一段字符串中的最长回文串。  因为数据量比较大，用原来的O（n^2）会爆。   小白上的O(n^2)解法代码：TLE啦~  #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        秋招最新大模型算法面试，熬夜都要肝完它
                                    
                                

                            

                            

                                

                                    秋招最新大模型算法面试，熬夜都要肝完它
                                

                                

                                    💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力  这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        怎么让1台电脑共享给7人同时流畅设计
                                    
                                

                            

                            

                                

                                    怎么让1台电脑共享给7人同时流畅设计
                                

                                

                                    在当今的创意设计与数字内容生产领域，图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能，成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限，比如只有一台高性能电脑时，如何高效地让七人同时流畅地进行设计工作，便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器（CPU）：选择多核、高线程的处理器，例如Intel的至强系列或AMD的Ry
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        dp算法练习题【8】
                                    
                                

                            

                            

                                

                                    dp算法练习题【8】
                                

                                

                                    不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。  示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2