当前位置: 首页 > news >正文

任务分配问题(回溯法)

算法设计

问题描述

有n(n≥1)个任务需要分配给n个人执行,每个任务只能分配给一个人,每个人只能执行一个任务。
第i个人执行第j个任务的成本是c[i][j](1≤i,j≤n)。求出总成本最小的分配方案
在这里插入图片描述

解题思路

回溯法解题的一般步骤
(1)针对给定的问题确定问题的解空间树,问题的解空间树应至少包含问题的一个解或者最优解。
(2)确定结点的扩展搜索规则
(3)以深度优先的方式搜索解空间树,并在搜索的过程中可以采用减枝函数来避免无效搜索。其中,深度优先方式可以选择递归回溯或者迭代(非递归)回溯

通过将问题进行适当的转化,得出解空间树为排列树,这棵树每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树,枚举每种可能的解的情况,找出能得到最小的花费结果。其中构造约束函数,可以删除一些不可能的解,从而大大提高程序效率

算法描述

(1)解空间
解空间为{x1,x2,x3,x4……,xn},其中xi=1,2,3,4……n,表示第i个人安排的任务
(2)解空间树
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

#include<stdio.h>
#include<cstring>
#include<queue>using namespace std;
#define MAXN 20		
#define INF 9999
//问题表示: 
int n=4;//人或任务个数 
int c[MAXN][MAXN]={{0,0,0,0,0},{0,9,2,7,8},{0,6,4,3,7},{0,5,8,1,8},{0,7,6,9,4}}; 
//求解结果表示: 
int x[MAXN]; 		//临时解
int cost=0;			//临时解的成本
int bestx[MAXN];	//最优解
int mincost=INF;	//最优解成本
bool worker[MAXN]; 	//表示任务是否已经分配人员 void dfs(int i)		//为第i个人员分配任务 
{if(i>n)			//如果达到叶子节点 {if(cost<mincost)		//当前成本小于最小成本mincost{mincost=cost;			//更新最小成本for(int j=1;j<=n;j++)	//遍历所有人员编号1~nbestx[j]=x[j];		//将最佳人员编号给bestx}}else{for(int j=1;j<=n;j++)	//遍历所有人员编号1~nif(!worker[j])			//如果没有分配任务{worker[j]=true;			//标记已经分配任务x[i]=j;					//将任务编号j分配给第i个人cost+=c[i][j];			//更新成本,加上分配任务成本dfs(i+1);				//调用dfs函数,分配下一个人员worker[j]=false;		//标记该人员未分配任务x[j]=0;					//任务编号清零,表示该人员未被分配任务cost-=c[i][j];			//更新当前成本,减去分配任务成本} } 
}
int  main(){memset(worker,0,sizeof(worker));				//memset函数将worker数组的所有元素初始化为0。dfs(1);											//寻找最优方案printf("最优方案\n");for(int k=1;k<=n;k++)							//从1循环到总人数nprintf("第%d个人安排任务%d\n",k,bestx[k]);	//输出第k个人的任务分配printf("总成本=%d\n",mincost);					//输出最小成本return 0;}

相关文章:

任务分配问题(回溯法)

算法设计 问题描述 有n&#xff08;n≥1&#xff09;个任务需要分配给n个人执行&#xff0c;每个任务只能分配给一个人&#xff0c;每个人只能执行一个任务。 第i个人执行第j个任务的成本是c[i][j]&#xff08;1≤i&#xff0c;j≤n&#xff09;。求出总成本最小的分配方案 …...

华为OD 字符串消除(100分)【java】A卷+B卷

华为OD统一考试A卷+B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目,A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载,请点击以下链接进入: 我用夸克网盘分享了「华为O…...

索引背后的数据结构——B+树

为什么要使用B树&#xff1f; 可以进行数据查询的数据结构有二叉搜索树、哈希表等。对于前者来说&#xff0c;树的高度越高&#xff0c;进行查询比较的时候访问磁盘的次数就越多。而后者只有在数据等于key值的时候才能进行查询&#xff0c;不能进行模糊匹配。所以出现了B树来解…...

面试用-常用注解

Configuration 注意由ConfigurationClassPostProcessor来处理ConfigurationClassPostProcessor执行这个后置处理 ConfigurationClassParser.parse执行这个方法里面会解析很多注解。1、Component 对于Component也是一样递归调用parse方法&#xff0c;一层层解析…...

【c++】跟webrtc学std array 4: H264PacketBuffer 包缓存

H264PacketBuffer m98代码:H264PacketBuffer 类似于PacketBuffer ,但仅用于H264// The H264PacketBuffer does the same job as the PacketBuffer but for H264 // only. To make it fit in with surronding code the PacketBuffer input/output // classes are used. 因此,…...

Nodejs Web数据库应用演示实例

Nodejs Web应用基础演示实例 Web数据库应用 一、服务器端 var express require(express); var app express(); var mysql require(mysql);//设置静态资源目录public app.use(express.static(__dirname /public));//创建mysql数据库访问连接&#xff08;数据库主机地址&a…...

Vue 中setup的特性

特性四&#xff1a;父传子组件传参【defineProps】&#xff1a; 父组件&#xff08;传递数据&#xff09;&#xff1a;利用自定义属性传递数据。 <template><h3>我是父组件</h3><hr /><Child :name"info.name" :age"info.age"…...

Peter算法小课堂—正整数拆分

大家可能会想&#xff1a;正整数拆分谁不会啊&#xff0c;2年级就会了&#xff0c;为啥要学啊 例题 正整数拆分有好几种&#xff0c;这里我们列举两种讲。 关系 我们看着第一幅图&#xff0c;头向左转90&#xff0c;记住你看到的图&#xff0c;再来看第二幅图&#xff0c;你…...

EDUSRC--简单打穿某985之旅

免责声明&#xff1a; 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直…...

vue2升级到vue2.7

vue2升级到vue2.7 小小的改进,大大的提升 只需要简单修改,开发体验得到大大提升. 为什么要升级Vue2.7 不能拒绝的理由: 组合式 API(解决mixins问题:命名冲突,隐式依赖)单文件组件内的 <script setup>语法模板表达式中支持 ESNext 语法(可选链:?.、空值合并:??)单文…...

【django2.0之Rest_Framework框架一】rest_framework序列器介绍

Django RestFramework(简称DRF) 提供了序列化器Serialzier的定义&#xff0c;可以帮助我们简化序列化与反序列化的过程&#xff0c;不仅如此&#xff0c;还提供丰富的类视图、扩展类、视图集来简化视图的编写工作。REST framework还提供了认证、权限、限流、过滤、分页、接口文…...

Mock 测试详解:什么是 Mock 测试

Mock测试 什么是 Mock &#xff1f; Mock 的意思就是&#xff0c;当你很难拿到源数据时&#xff0c;你可以使用某些手段&#xff0c;去获取到跟源数据相似的假数据&#xff0c;拿着这些假数据&#xff0c;前端可以先行开发&#xff0c;而不需要等待后端给了数据后再开发。 Mo…...

Android端自定义铃声

随着移动应用竞争进入红海时代&#xff0c;如何在APP推送中别出心裁显得尤为重要。例如对自己的APP推送赋予独特的推送铃声&#xff0c;能够给用户更加理想的使用体验。 1、个性化提醒铃声有助于当收到特定类型的消息时&#xff0c;用户能够立刻识别出来。 2、不同的推送铃声…...

docker mysql 5.7

1.docker 安装mysql 5.7 docker pull mysql:5.72.配置容器MySQL数据、配置、日志挂载宿主机目录 # 宿主机创建数据存放目录映射到容器 mkdir -p /usr/local/docker_data/mysql/data# 宿主机创建配置文件目录映射到容器 mkdir -p /usr/local/docker_data/mysql/conf #(需要在…...

MySQL中如何进行分库分表的设计和实现?

分库分表是一种常用的数据库扩展方式&#xff0c;可以提高数据库的并发处理能力和扩展性&#xff0c;下面是分库分表的设计和实现的一般步骤&#xff1a; 数据库选择&#xff1a;选择合适的数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;如MySQL&#xff0c;支持分库…...

linux 安装谷歌浏览器和对应的驱动

创建文件install-google-chrome.sh #! /bin/bash# Copyright 2017-present: Intoli, LLC # Source: https://intoli.com/blog/installing-google-chrome-on-centos/ # # Redistribution and use in source and binary forms, with or without # modification, are permitted p…...

FPGA的通用FIFO设计verilog,1024*8bit仿真,源码和视频

名称&#xff1a;FIFO存储器设计1024*8bit 软件&#xff1a;Quartus 语言&#xff1a;Verilog 本代码为FIFO通用代码&#xff0c;其他深度和位宽可简单修改以下参数得到 reg [7:0] ram [1023:0];//RAM。深度1024&#xff0c;宽度8 代码功能&#xff1a; 设计一个基于FPGA…...

攻防世界web篇-backup

这是链接中的网页&#xff0c;只有一句话 试着使用.bak点缀看看是否有效 这里链接中加上index.php.bak让下在东西 是一个bak文件&#xff0c;将.bak文件改为.php文件试试 打开.php文件后就可以得到flag值...

uni-app:js二维数组与对象数组之间的转换

一、二维数组整理成对象数组 效果 [ ["前绿箭","DI10","RO1"], ["前红叉","DI2","RO2"], ["后绿箭","DI12","RO3"], ["后红叉","DI4","RO6"] ] …...

15-bean生命周期,循环依赖

文章目录 1. bean生命周期 1. bean生命周期...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

比特币:固若金汤的数字堡垒与它的四道防线

第一道防线&#xff1a;机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”&#xff08;Hashing&#xff09;就是一种军事级的加密术&#xff08;SHA-256&#xff09;&#xff0c;能将信函内容&#xff08;交易细节&#xf…...

信息系统分析与设计复习

2024试卷 单选题&#xff08;20&#xff09; 1、在一个聊天系统(类似ChatGPT)中&#xff0c;属于控制类的是&#xff08;&#xff09;。 A. 话语者类 B.聊天文字输入界面类 C. 聊天主题辨别类 D. 聊天历史类 ​解析 B-C-E备选架构中分析类分为边界类、控制类和实体类。 边界…...