任务分配问题(回溯法)
算法设计
问题描述
有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(n≥1)个任务需要分配给n个人执行,每个任务只能分配给一个人,每个人只能执行一个任务。 第i个人执行第j个任务的成本是c[i][j](1≤i,j≤n)。求出总成本最小的分配方案 …...
华为OD 字符串消除(100分)【java】A卷+B卷
华为OD统一考试A卷+B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目,A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载,请点击以下链接进入: 我用夸克网盘分享了「华为O…...
索引背后的数据结构——B+树
为什么要使用B树? 可以进行数据查询的数据结构有二叉搜索树、哈希表等。对于前者来说,树的高度越高,进行查询比较的时候访问磁盘的次数就越多。而后者只有在数据等于key值的时候才能进行查询,不能进行模糊匹配。所以出现了B树来解…...
面试用-常用注解
Configuration 注意由ConfigurationClassPostProcessor来处理ConfigurationClassPostProcessor执行这个后置处理 ConfigurationClassParser.parse执行这个方法里面会解析很多注解。1、Component 对于Component也是一样递归调用parse方法,一层层解析…...
【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数据库访问连接(数据库主机地址&a…...
Vue 中setup的特性
特性四:父传子组件传参【defineProps】: 父组件(传递数据):利用自定义属性传递数据。 <template><h3>我是父组件</h3><hr /><Child :name"info.name" :age"info.age"…...
Peter算法小课堂—正整数拆分
大家可能会想:正整数拆分谁不会啊,2年级就会了,为啥要学啊 例题 正整数拆分有好几种,这里我们列举两种讲。 关系 我们看着第一幅图,头向左转90,记住你看到的图,再来看第二幅图,你…...
EDUSRC--简单打穿某985之旅
免责声明: 文章中涉及的漏洞均已修复,敏感信息均已做打码处理,文章仅做经验分享用途,切勿当真,未授权的攻击属于非法行为!文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直…...
vue2升级到vue2.7
vue2升级到vue2.7 小小的改进,大大的提升 只需要简单修改,开发体验得到大大提升. 为什么要升级Vue2.7 不能拒绝的理由: 组合式 API(解决mixins问题:命名冲突,隐式依赖)单文件组件内的 <script setup>语法模板表达式中支持 ESNext 语法(可选链:?.、空值合并:??)单文…...
【django2.0之Rest_Framework框架一】rest_framework序列器介绍
Django RestFramework(简称DRF) 提供了序列化器Serialzier的定义,可以帮助我们简化序列化与反序列化的过程,不仅如此,还提供丰富的类视图、扩展类、视图集来简化视图的编写工作。REST framework还提供了认证、权限、限流、过滤、分页、接口文…...
Mock 测试详解:什么是 Mock 测试
Mock测试 什么是 Mock ? Mock 的意思就是,当你很难拿到源数据时,你可以使用某些手段,去获取到跟源数据相似的假数据,拿着这些假数据,前端可以先行开发,而不需要等待后端给了数据后再开发。 Mo…...
Android端自定义铃声
随着移动应用竞争进入红海时代,如何在APP推送中别出心裁显得尤为重要。例如对自己的APP推送赋予独特的推送铃声,能够给用户更加理想的使用体验。 1、个性化提醒铃声有助于当收到特定类型的消息时,用户能够立刻识别出来。 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中如何进行分库分表的设计和实现?
分库分表是一种常用的数据库扩展方式,可以提高数据库的并发处理能力和扩展性,下面是分库分表的设计和实现的一般步骤: 数据库选择:选择合适的数据库管理系统(DBMS),如MySQL,支持分库…...
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仿真,源码和视频
名称:FIFO存储器设计1024*8bit 软件:Quartus 语言:Verilog 本代码为FIFO通用代码,其他深度和位宽可简单修改以下参数得到 reg [7:0] ram [1023:0];//RAM。深度1024,宽度8 代码功能: 设计一个基于FPGA…...
攻防世界web篇-backup
这是链接中的网页,只有一句话 试着使用.bak点缀看看是否有效 这里链接中加上index.php.bak让下在东西 是一个bak文件,将.bak文件改为.php文件试试 打开.php文件后就可以得到flag值...
uni-app:js二维数组与对象数组之间的转换
一、二维数组整理成对象数组 效果 [ ["前绿箭","DI10","RO1"], ["前红叉","DI2","RO2"], ["后绿箭","DI12","RO3"], ["后红叉","DI4","RO6"] ] …...
15-bean生命周期,循环依赖
文章目录 1. bean生命周期 1. bean生命周期...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
