西南交通大学【算法分析与设计实验3】

实验3.3 任务分配问题

实验目的

(1)理解穷举法典型算法的求解过程。

(2)学习穷举法的时间复杂度分析方法,并通过实验验证算法的执行效率。

(3)学会如何利用穷举法求解具体问题,了解穷举法的局限性。

实验任务

(1)利用穷举法手工完成实验3.3测试用例的求解。

(2)用C++语言实现该算法并进行测试。

(3)撰写实验报告,实验报告内容包括实验目的、实验任务、实验环境、实验步骤、实验结果和实验总结等部分。

实验步骤及结果

实验预习

根据样例输入采用穷举法求出一种总成本最小的分配方案

该问题的解空间树是排列树

约束条件:遍历到的任务没有被执行,如果不满足则continue

目标函数:设每个人执行所分配任务的成本是 xi

则f(x) = min\sum xi

样例对应搜索空间树:

其中0代表未分配任务

通过图可以看出第一个人执行第二个任务,第二个人执行第一个任务,第三个人执行第三个任务,第四个人执行第四个任务成本最小。

用C/C++语言实现的源代码

#include <iostream>
using namespace std;
// 任务成本
int c[100][100];
// 人数(任务数),初始化为1
int n = 1;
// 最小成本,初始化为10000
int min_cost = 10000;
// 判断任务是否被执行的数组
int used[100];
// 每个人执行哪个人物的数组
int res[100];
// 回溯
void backtracking(int res[], int used[], int num){
    // 如果res中结果数量达到人数则退出递归
    if(num == n){
        // 计算此种任务分配的成本
        int sum = 0;
        for(int i = 1;i <= n;++i){
            sum += c[i][res[i]];
        }
        // 如果成本比最小成本小更新最小成本
        if(sum < min_cost){
            min_cost = sum;
        }
        return;
    }
    // 遍历used数组往下递归
    for(int i = 1;i <= n;++i){
        // 如果任务已执行continue
        if(used[i] == 1){
            continue;
        }
        // 执行此任务
        used[i] = 1;
        // 执行人数加1
        num++;
        // 将任务分配给此人
        res[num] = i;
        // 向下递归
        backtracking(res, used, num);
        // 回溯
        res[num] = 0;
        num--;
        used[i] = 0;
    }
}
int main(void){
    // 读取第一行数据
    char temp;
    int number = 0;
    // 读取第一行数据得到人数(任务数)
    while(temp = getchar()){
        if(temp == ' '){
            c[1][n] = number;
            number = 0;
            n++;
        }else if(temp == '\n'){
            c[1][n] = number;
            number = 0;
            break;
        }else{
            number = number * 10 + (temp - '0');
        }
    }
    // 读取剩下的数据
    for(int i = 2;i <= n;++i){
        for(int j = 1;j <= n;++j){
            cin>>c[i][j];
        }
    }
    // 初始化res数组和used数组
    for(int i = 1;i <= n;++i){
        res[i] = 0;
        used[i] = 0;
    }
    // 开始递归
    backtracking(res, used, 0);
    // 输出最小成本
    cout<<min_cost<<endl;
    system("pause");
    return 0;
}

上机实验

上机调试,验证你的求解过程是否正确,写出验证过程

在程序添加将每次方案和方案成本输出代码来验证求解过程是否正确,输入已给样例,得到输出截图:

通过输出截图可知求解过程正确

设计新的测试用例,对程序进行进一步验证

用例输入:

1 2 3 4 5

5 1 2 3 4

4 5 1 2 3

3 4 5 1 2

2 3 4 5 1

输出截图(方案过多直接输出最小成本):

通过输出截图易知算法正确

完成实验3.2的实验预习1

实验总结

通过具体学习了排列这种典型的穷举算法的求解过程以及程序框架,分析了其算法的求解过程,时间复杂度分析方法,以及如何设计穷举法解决实际问题。通过此次实验,正确理解了穷举法的特点以及实际运用中的局限性,并为以后得学习打下基础。

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

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

相关文章

51单片机嵌入式开发:STC89C52操作8八段式数码管原理

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 STC89C52操作8八段式数码管原理 1 8位数码管介绍1.1 8位数码管概述1.2 8位数码管原理1.3 应用场景 2 原理图图解2.1 74HC573原理2.2 74HC138原理2.3 数码管原理 3 数码管程序…

现代智能宠物喂食器方案定制

现代智能宠物喂食器不仅具备定时喂食功能&#xff0c;帮助宠物主人管理宠物的饮食时间和食量&#xff0c;还加入了录音功能和摄像头&#xff0c;使得宠物主人即使不在家也能与宠物保持互动&#xff0c;并实时监控宠物的状况。此外&#xff0c;一些产品还具备紧急预警功能&#…

Docker加速器配置指南:提升镜像下载速度的秘诀 加速安装Mysql Redis ES

在安装 Docker 镜像时&#xff0c;由于官方镜像下载速度较慢&#xff0c;我们可以使用阿里云的镜像加速器来提升下载速度。 使用阿里云镜像加速器 首先&#xff0c;找到并配置阿里云的镜像加速器。安装教程如下&#xff1a; 登录阿里云&#xff0c;进入容器镜像服务。直达链…

PyTorch之nn.Module与nn.functional用法区别

文章目录 1. nn.Module2. nn.functional2.1 基本用法2.2 常用函数 3. nn.Module 与 nn.functional3.1 主要区别3.2 具体样例&#xff1a;nn.ReLU() 与 F.relu() 参考资料 1. nn.Module 在PyTorch中&#xff0c;nn.Module 类扮演着核心角色&#xff0c;它是构建任何自定义神经网…

大数据------JavaWeb------JSP(完整知识点汇总)

JSP 定义 JSP&#xff08;Java Server Pages&#xff09;&#xff0c;即Java服务端页面。它是一种动态的网页技术&#xff0c;其中可以定义HTML、CSS、JS等静态内容&#xff0c;还可以定义Java代码的动态内容JSP HTML Java 说白了JSP就是一个页面&#xff0c;它既可以写HTML标…

【每日刷题】Day79

【每日刷题】Day79 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 1619. 删除某些元素后的数组均值 - 力扣&#xff08;LeetCode&#xff09; 2. 1365. 有多少小于当前…

Python UUID模块:深入理解与使用技巧

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…

Spark入门教程(非常详细)从零基础入门到精通,看完这一篇就够了

文章目录 引言1. Spark 基础 1.1 Spark 为何物1.2 Spark VS Hadoop1.3 Spark 优势及特点 1.3.1 优秀的数据模型和丰富计算抽象1.3.2 完善的生态圈-fullstack1.3.3 spark的特点 1.4 Spark 运行模式 2. Spark Core 2.1 RDD详解 2.1.1 RDD概念2.1.2 RDD属性2.1.3 RDD API 2.1.3.1…

还有人不会挑智能猫砂盆?详细测评热门品牌糯雪、空气萝卜、CEWEY!

在现代家居生活中&#xff0c;宠物已成为许多家庭不可或缺的一员&#xff0c;而猫砂盆作为猫咪日常如厕的重要工具&#xff0c;选择什么类型的智能猫砂盆更是关乎猫咪健康与生活质量的关键。而市面上的智能猫砂盆品类众多&#xff0c;令人在挑选的时候眼花缭乱&#xff0c;不知…

监控平台zabbix对接grafana

目录 1.安装grafana并启动 2.浏览器访问 3.导入zabbix数据&#xff0c;对接grafana 4.如何导入模板 5.使用zabbix监控nginx并发量连接数 5.1 修改nginx配置 5.2 编写监控数据脚本 5.3 设置键值 5.4 在zabbix web端完成自定义监控项 5.5 连接到grafana 以上一篇博客&l…

GCN结合Transformer炸场!性能暴涨74%,效率翻3倍

最近发现了两篇效果很妙的GCN结合Transformer的最新工作&#xff0c;分享给大家&#xff1a; MP-GT&#xff1a;通过结合GCN和Transformer方法来增强App使用预测的准确性&#xff0c;实现了74.02%的性能提升&#xff0c;且训练时间减少了79.47%。 MotionAGFormer&#xff1a;结…

Dubbo简介

Apache Dubbo是一款高性能、轻量级的开源服务框架。 1.单体架构 比如现在有一个学生成绩管理平台&#xff0c;里面有学生管理&#xff0c;教师管理&#xff0c;成绩管理。然后将这个系统打包上线&#xff0c;部署在一个2核4G的服务器上&#xff0c;但是现在用户对成绩管理模块…

Shell Expect自动化交互(示例)

Shell Expect自动化交互 日常linux运维时&#xff0c;经常需要远程登录到服务器&#xff0c;登录过程中需要交互的过程&#xff0c;可能需要输入yes/no等信息&#xff0c;所以就用到expect来实现交互。 关键语法 ❶&#xff3b;#!/usr/bin/expect&#xff3d; 这一行告诉操…

民宿小程序开发,在线预订模式

一、开发背景 如今&#xff0c;随着互联网技术的快速发展&#xff0c;大众的生活消费都集中在了手机上&#xff0c;通过手机进行各种活动&#xff0c;同时也包括了预订酒店民宿&#xff0c;由此&#xff0c;民宿预约小程序出现在了大众的生活中。 二、民宿小程序特点 民宿小…

怎么参与场外期权?

今天期权懂带你了解怎么参与场外期权&#xff1f; 目前个人投资者暂时还不能直接参与场外个股期权&#xff0c;因为场外个股期权现在只能机构来进行交易。 所以个人投资者目前只能通过机构通道来进行操作&#xff0c;类似期权懂&#xff0c;找到期权懂经理&#xff0c;然后通…

深入浅出:C语言线程以及线程锁

目录 线程和线程锁概念 线程锁的概念 线程的特点 线程的使用 创建线程 pthread_create 回收线程pthread_join 退出线程 pthread_exit 线程锁的使用 线程同步之互斥锁&#xff08;Mutex&#xff09; 初始化互斥锁 获取互斥锁 释放互斥锁 销毁互斥锁 初始化条件变量…

SSMOA办公系统-计算机毕业设计源码19159

摘 要 随着现代信息技术的快速发展以及企业规模不断扩大&#xff0c;实现办公线上流程自动化已成为提升企业核心竞争力的关键。本文主要介绍的是利用Spring、SpringMVC和MyBatis&#xff08;简称为&#xff1a;SSM&#xff09;框架&#xff0c;MySQL数据库等先进的互联网开源技…

X86 +PC104+支持WinCE5.0,WinCE6.0,DOS,WinXP, QNX等操作系统,工业控制数据采集核心模块板卡定制

CPU 模块 是一款基于RDC 3306的SOM Express模块。RDC 3306这款X86架构的CPU是一款性能高、稳定性强的处理器。 它是一款灵活精巧的主板&#xff08;尺寸为91.8mm68.6mm&#xff09;&#xff0c;可以灵活的运用于用户的底板&#xff0c;节约开发成本。模块的接插件使用插针形式…

基于PHP花涧订购系统的设计与实现-计算机毕业设计源码00332

摘 要 近年来&#xff0c;电子商务的快速发展引起了行业和学术界的高度关注。花涧订购系统旨在为用户提供一个简单、高效、便捷的花卉购物体验&#xff0c;它不仅要求用户清晰地查看所需信息&#xff0c;而且还要求界面设计精美&#xff0c;使得功能与页面完美融合&#xff0c;…

固定网国内数据传送业务经营许可证

一、国内固定网数据传送业务是什么&#xff1f; 固定网国内数据传送业务是指互联网数据传送业务以外的&#xff0c;在固定网中以有线方式提供的国内端到端数据传送业务。主要包括基于IP承载网、ATM网、X.25分组交换网、DDN网、帧中继网络的数据传送业务等。该业务属于A2类基础…