西南交大swjtu算法实验3.3|穷举法

1.实验目的

通过具体例子学习排列这种典型的穷举算法的求解过程以及程序框架,分析其算法的求解过程,以及如何设计穷举法解决实际问题。通过本实验,理解穷举法的特点以及实际应用中的局限性。

 

2.实验任务

有n (n>=1)个任务需要分配给n个人执行,每个任务只能分配给一个人,每个人只能执行一个任务,第i个人执行第j个任务的成本是c[i][j](1<=i ,j<=n)。求出总成本最小的一种分配方案。

输入:输入n行,每行有n个正整数。第i行的第j个数表示第i个人执行第j个任务所需要的成本。

输出:输出一个正整数,表示最小的总成本。样例输入:

9 2 7 8

6 4 3 7

5 8 1 8

7 6 9 4

实验预习:

(1)根据样例输入,采用穷举法求出一种总成本最小的分配方案,写出求解过程。

(2)编写程序,采用穷举法求解上述问题。

上机实验:

(3)上机调试,验证你的求解过程是否正确,并设计新的测试用例,对程序进行进一步验证,写出验证过程。

(4)撰写实验报告,内容包括:实验目的、实验任务、实验环境、实验步骤、实验结果及其分析以及实验总结等部分内容。

3.程序代码

#include<conio.h>
#include<iostream>
#include<vector>
#define N 100
void Perm(int*, int, int);
void Swap(int&, int&);
using namespace std;
int mincost{ 99999 };
int c[N][N]{ 0 };//执行成本
vector<vector<int>> result;
vector<int> minpath;
int main()
{
	int list[N]{0}, n;
	cout << "input n:";
	cin >> n;
	cout << "input cost:";
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> c[i][j];
		}

	}
	for (int i = 1; i <= n; i++)
	{
		list[i] = i;
	}

	Perm(list, 1, n);
	cout << mincost;
	cout << endl;
	vector<int>::iterator it = minpath.begin();
	while (it != minpath.end())
	{
		cout << *it;
		it++;
	}
	cout << endl;
	/*for (int i = 0; i < result.size(); i++)
	{
		for (int j = 0; j < result[i].size(); j++)
		{
			cout << result.at(i).at(j);
		}
		cout << endl;
	}*/
	return 0;
}
void Perm(int* list, int k, int m) {
	int i;
	if (k == m) {
		int curcost{ 0 };
		vector<int> path;
		for (i = 1; i <= m; i++)
		{
		   curcost += c[i][list[i]];
		   path.push_back(list[i]);//printf("%d ", list[i]);
		}
		if (curcost < mincost)
		{
			mincost = curcost;
			minpath = path;
		}
		result.push_back(path);
	}
	else {
		for (i = k; i <= m; i++)
		{
			Swap(list[k], list[i]);
			Perm(list, k + 1, m);
			Swap(list[k], list[i]);
		}
	}
	return;
}

void Swap(int& i, int& j)
{
	int temp; temp = i; i = j; j = temp;
	return;
}

4.测试结果

 

注:输出的第二排为最低成本时每个人对应做的任务

测试1:

n=4,成本矩阵:

9 2 7 8

6 4 3 7

5 8 1 8

7 6 9 4

运行结果:

79f15fe035f54712bf5dfc25de6c59e7.png

测试2:

n=3,成本矩阵为:

250 400 350

400 600 350

200 400 250

运行结果:

 9f1a3c0a55eb4bf7914d3f3946822cc0.png

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505647.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Visual Studio 2022 中VLD库如何安装

GitHub链接 Release v2.5.1 KindDragon/vld 点击可执行程序进行下载 点击可执行程序进行安装 双击打开 一直点击next即可完成安装&#xff08;不用在意安装路径&#xff0c;总共不到2MB&#xff09; 如果GitHub无法打开&#xff0c;可以私信我发你安装包直接安装

fpga_awb

色温: sesor原始图像中的白色如果不经AWB处理&#xff0c;在高色温(如阴天)下偏蓝&#xff0c;在低色温下偏黄。 引入白平衡算法 而AWB的核心就是调整图像色温&#xff0c;使得摄像头采集的图像更加真实&#xff0c;达到人眼观察的效果。 白平衡一般通过调节传感器输出图像RGB…

【aws】架构图工具推荐

碎碎念 以前以为日本冰箱论是个梗&#xff0c;结果居然是真的。用光盘传真其实还能理解&#xff08;毕竟我也喜欢电子古董2333&#xff09;&#xff0c;但是画架构图居然用的是excel&#xff0b;截图&#xff01;啊苍天呐&#xff0c;然后看到隔壁工位用excel画web原型又感觉释…

svg实现环形进度条

实现效果图&#xff1a; svg相关知识 这里只介绍本次用到的元素&#xff0c;更多详情&#xff1a;SVG&#xff1a;可缩放矢量图形 defs&#xff1a;定义需要重复利用的图形元素linearGradient&#xff1a;定义线性渐变&#xff0c;用来图形元素的填充或描边使用stop&#x…

hcip综合实验2

目录 实验拓扑&#xff1a; 实验要求&#xff1a; 实验思路&#xff1a; 实验步骤&#xff1a; 1.配置设备接口IP 2.通过配置缺省路由让公网互通 3.配置ppp 1.R1和R5间的ppp的PAP认证&#xff1b; 2.R2与R5之间的ppp的CHAP认证; 3. R3与R5之间的HDLC封装; 4.构建R1、…

动态规划之子序列(三)

583. 两个字符串的删除操作 给定两个单词 word1 和 word2&#xff0c;找到使得 word1 和 word2 相同所需的最小步数&#xff0c;每步可以删除任意一个字符串中的一个字符。 示例&#xff1a; 输入: “sea”, “eat” 输出: 2 解释: 第一步将"sea"变为"ea"…

c实现猜数游戏(猜不对可是要自动帮你电脑关机)

接下来的日子会顺顺利利&#xff0c;万事胜意&#xff0c;生活明朗-----------林辞忧 前言 猜数字游戏作为一个基础的C程序小项目&#xff0c;实现简单&#xff0c;可以帮助我们巩固很多知识&#xff0c;作为扩展接下来我们实现一个自定猜数次数&#xff0c;用完次数电脑自动…

keepalived+LVS高可用部署

目录 一.两台设备&#xff08;2.130和2.133&#xff09;作为调度器&#xff0c;前主后备 1.部署keepalived 2.修改配置文件准备启动 3.配置keepalived的系统日志并启动 二.模拟调度器掉点和web服务进程丢失 1.调度器掉点 2.当类似于httpd这种网站服务掉点 三.以三种健康…

【从前端入门到全栈】前端框架之核心概念

大家好&#xff0c;我是江辰&#xff0c;从前端入门到全栈是我全新系列文章&#xff0c;从去年一直囔囔着要写&#xff0c;今年总算开始了&#xff01;预计在10篇左右。知识面从 前端&#xff0c;后端&#xff0c;运维&#xff0c;脚本等&#xff0c;都有涉及&#xff0c;主打一…

Spark-Scala语言实战(9)

之前的文章中&#xff0c;我们学习了如何在spark中使用RDD方法的flatMap,take,union。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵的点赞&#xff0c;谢谢。 Spark-Scala语言实战&am…

数据分析web可视化神器---streamlit框架,无需懂前端也能搭建出精美的web网站页面

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属的专栏&#xff1a;数据分析系统化教学&#xff0c;零基础到进阶实战 景天的主页&#xff1a;景天科技苑 文章目录 Streamlit什么是streamli…

基于springboot+vue实现的学校田径运动会管理系统

作者主页&#xff1a;Java码库 主营内容&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 技术选型 【后端】&#xff1a;Java 【框架】&#xff1a;spring…

CommunityToolkit.Mvvm----配置

一、介绍&#xff1a; CommunityToolkit.Mvvm 包&#xff08;又名 MVVM 工具包&#xff0c;以前称为 Microsoft.Toolkit.Mvvm&#xff09;是一个现代、快速和模块化的 MVVM 库。 它是 .NET 社区工具包的一部分&#xff0c;围绕以下原则生成&#xff1a; 独立于平台和运行时 - …

MySQL MHA高可用配置以及故障切换

目录 什么是 MHA 什么是 MHA MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。解决主从架构中的主服务器的单点问题 MySQL故障切换过程中&#xff0c;MHA能做到0-30秒内自动…

计算机网络:数据链路层 - 封装成帧 透明传输 差错检测

计算机网络&#xff1a;数据链路层 - 封装成帧 & 透明传输 & 差错检测 数据链路层概述封装成帧透明传输差错检测 数据链路层概述 从数据链路层来看&#xff0c;主机 H1 到 H2 的通信可以看成是在四段不同的链路上的通信组成的&#xff0c;所谓链路就是从一个节点到相邻…

python distribute是什么

Python的包管理工具常见的有easy_install, setuptools, 还有pip, distribute&#xff0c;那麽这几个工具有什么关系呢&#xff0c;看一下下面这个图就明白了&#xff1a; 可以看到distribute是setuptools的替代方案&#xff0c;pip是easy_install的替代方案。 Distribute提供一…

古代书法名家墨迹范本,中国法书碑帖图片合集

一、图片描述 在书法作品里&#xff0c;什么是法书&#xff1f;这是书法用语&#xff0c;又称法帖&#xff0c;学习书法可以作为楷模的范本&#xff0c;以及对古代名家墨迹的敬称&#xff0c;或以此誉称表达对书法作者的尊重之意&#xff0c;法书墨迹是最能反映古代书法艺术面…

Windows-安装infercnv包(自备)

目录 安装基础 ①安装JAGS a,找到适配版本 b&#xff0c;install for me only安装路径 ②安装"rjags"包 ③安装inferCNV 安装基础 版本&#xff1a; R version 4.2.2 (2022-10-31 ucrt) -- "Innocent and Trusting"安装的JAGS版本为JAGS 4.3.1 首…

Nginx_简介 + Linux系统下详细安装教程指路

安装教程指路 可参看该视频【尚硅谷Nginx教程&#xff08;亿级流量nginx架构设计&#xff09;】 https://www.bilibili.com/video/BV1yS4y1N76R/?p2&share_sourcecopy_web&vd_source4c2f33f3ba1a0dd45bfdf574befd0069 的p2-p7。从安装centos虚拟机到在虚拟机上安装ng…

考研数学|听完一遍汤家凤基础,1800都没思路,怎么办?

看了我这篇回答&#xff0c;保证你可以顺利的做1800题&#xff01; 如果你听了汤家凤老师的课&#xff0c;但是做题没思路&#xff0c;请不要担心&#xff0c;也不要急着换老师&#xff0c;你很有可能是方法错了。 请你反思一下&#xff1a; 1、你是不是听完课立刻就去做题。…