西南交大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

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HarmonyOS 应用开发之FA模型与Stage模型应用组件

应用配置文件概述&#xff08;FA模型&#xff09; 每个应用项目必须在项目的代码目录下加入配置文件&#xff0c;这些配置文件会向编译工具、操作系统和应用市场提供描述应用的基本信息。 应用配置文件需申明以下内容&#xff1a; 应用的软件Bundle名称&#xff0c;应用的开发…

使用Python实现对word的批量操作

Python在平时写写小工具真是方便快捷&#xff0c;Pyhon大法好。以下所有代码都是找了好多网上的大佬分享的代码按照自己的需求改的。 调用的库为Python-docx、win32com、PyPDF2、xlwings&#xff08;操作excel&#xff09;。 因为公司的任务要对上千个word文件进行批量操作&a…

JAVAEE之网络编程

1.网络编程 网络编程&#xff0c;指网络上的主机&#xff0c;通过不同的进程&#xff0c;以编程的方式实现网络通信&#xff08;或称为网络数据传输&#xff09;。 当然&#xff0c;我们只要满足进程不同就行&#xff1b; 所以即便是同一个主机&#xff0c;只要是不同进程&am…

【论文阅读】ELA: Efficient Local Attention for Deep Convolutional Neural Networks

&#xff08;ELA&#xff09;Efficient Local Attention for Deep Convolutional Neural Networks 论文链接&#xff1a;ELA: Efficient Local Attention for Deep Convolutional Neural Networks (arxiv.org) 作者&#xff1a;Wei Xu, Yi Wan 单位&#xff1a;兰州大学信息…

C语言-文件操作

&#x1f308;很高兴可以来阅读我的博客&#xff01;&#x1f31f;我热衷于分享&#x1f58a;学习经验&#xff0c;&#x1f3eb;多彩生活&#xff0c;精彩足球赛事⚽&#x1f517;我的CSDN&#xff1a; Kevin ’ s blog&#x1f4c2;专栏收录&#xff1a;C预言 1. 文件的作用 …

基于spark的大数据分析预测地震受灾情况的系统设计

基于spark的大数据分析预测地震受灾情况的系统设计 在本篇博客中,我们将介绍如何使用Apache Spark框架进行地震受灾情况的预测。我们将结合数据分析、特征工程、模型训练和评估等步骤,最终建立一个预测模型来预测地震造成的破坏程度,同时使用可视化大屏的方式展示数据的分布…

docker-compose运行springinitializr用来创建springboot2

前言 spring initializr官方的地址是: https://start.spring.io/ &#xff0c;这是一个用来创建springboot脚手架的一个工具&#xff0c;但是目前这个工具已经更新到springboot3&#xff0c;而我还没学springboot3&#xff0c;目前还想继续创建springboot2&#xff0c;我就想能…

Unity类银河恶魔城学习记录11-10 p112 Items drop源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili ItemObject_Trigger.cs using System.Collections; using System.Collecti…

Gin入门指南:从零开始快速掌握Go Web框架Gin

官网:https://gin-gonic.com/ GitHub:https://github.com/gin-gonic 了解 Gin Gin 是一个使用 Go 语言开发的 Web 框架,它非常轻量级且具有高性能。Gin 提供了快速构建 Web 应用程序所需的基本功能和丰富的中间件支持。 以下是 Gin 框架的一些特点和功能: 快速而高效:…

设计模式-结构型-享元模式Flyweight

享元模式的特点&#xff1a; 享元模式可以共享相同的对象&#xff0c;避免创建过多的对象实例&#xff0c;从而节省内存资源 使用场景&#xff1a; 常用于需要创建大量相似的对象的情况 享元接口类 public interface Flyweight { void operate(String extrinsicState); } 享…

信息工程大学第五届超越杯程序设计竞赛(同步赛)题解

比赛传送门 博客园传送门 c 模板框架 #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc.h> #define rep(i,a,b) for (int ia;i<b;i) #define per(i,a,b) for (int ia;i>b;--i) #define se second #define fi first #define e…

【C++庖丁解牛】自平衡二叉搜索树--AVL树

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 前言1 AVL树的概念2. AVL…

Solidity Uniswap V2 Router swapTokensForExactTokens

最初的router合约实现了许多不同的交换方式。我们不会实现所有的方式&#xff0c;但我想向大家展示如何实现倒置交换&#xff1a;用未知量的输入Token交换精确量的输出代币。这是一个有趣的用例&#xff0c;可能并不常用&#xff0c;但仍有可能实现。 GitHub - XuHugo/solidit…

基础布局之RelativeLayout相对布局

目录 概述一、属性分类二、父容器定位属性2.1 示例12.2 示例2 三、相对定位属性3.1 示例13.2 示例23.3 示例3 概述 相对布局&#xff08;RelativeLayout&#xff09;是一种根据父容器和兄弟控件作为参照来确定控件位置的布局方式。 使用相对布局&#xff0c;需要将布局节点改成…

Spring Boot 使用 Redis

1&#xff0c;Spring 是如何集成Redis的&#xff1f; 首先我们要使用jar包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency><dependency><gro…

基于ssm校园教务系统论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对校园教务信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差…

Windows 11 专业版 23H2 Docker Desktop 下载 安装 配置 使用

博文目录 文章目录 Docker Desktop准备系统要求 (WSL 2 backend)在 Windows 上打开 WSL 2 功能先决条件开启 WSL 2 WSL下载安装启动配置使用镜像 Image卷积 Volumes容器 Containers 命令RedisMySQLPostGreSQL Docker Desktop Overview of Docker Desktop Docker Desktop 疑难解…

每日面经分享(pytest入门)

1. pytest具有什么功能 a. 自动发现和执行测试用例&#xff1a;pytest可以自动发现项目中的测试文件和测试函数&#xff0c;无需手动编写测试套件或测试运行器。 b. 丰富的断言函数&#xff1a;pytest提供了丰富的断言函数&#xff0c;方便地验证测试结果是否符合预期。断言函…

隐私计算实训营学习五:隐语PSI介绍及开发指南

文章目录 一、SPU 实现的PSI介绍1.1 PSI定义和种类1.1.1 PSI定义和种类1.1.2 隐语PSI功能分层 1.2 SPU 实现的PSI介绍1.2.1 半诚实模型1.2.2 PSI实现位置 二、SPU PSI调度架构三、Secretflow PSI开发指南四、隐语PSI后续计划 一、SPU 实现的PSI介绍 1.1 PSI定义和种类 1.1.1 …

C++心决之命名空间、重载函数和引用

目录 1. C关键字(C98) 2. 命名空间 2.1 命名空间定义 2.2 命名空间使用 3. C输入&输出 4. 缺省参数 4.1 缺省参数概念 4.2 缺省参数分类 5. 函数重载 5.1 函数重载概念 5.2 C支持函数重载的原理--名字修饰(name Mangling) 6. 引用 6.1 引用概念 6.2 引用特性…