工作分配问题【回溯算法】-程序员宅基地

Problem Description

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为 $c_{ij}$ 。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。
设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

Input
输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。
Output
将计算出的最小总费用输出。

Sample Input

Sample Output

解题思路

为工作 i 安排第 j 个人的解决方法与“运动员最佳匹配问题”类似，让一方选另一方，这样就可以构成一棵排列树。我们让工作“选”人，那排列树的结点代表人，而层就代表工作。如下图左上角的G1表示工人1，且在第一层，表示为工作 1 安排第 1 个人，即将工作1分配给工人1。

样例分析

在这里插入图片描述

注：由上可知，最小值可能有多个，但效果一样，最终返回的都是9。

代码实现

#include <bits/stdc++.h>
using namespace std;

int n;
int pay[21][21];   //pay[i][j]表示将工作i分配给第j个人的费用为pay[i][j]
int Min=INT_MAX;   //因为要求最小值，所以将Min初始化为最大整数（int型）
int sum=0;   //记录搜索过程中得到的工作费用和
int book[21];   //用于标记一个人是否已被分配工作：book[i]=0表示没有被分配工作；book[i]=1表示已经被分配工作

void dfs(int t)
{
    
    if(t>=n)   //已经到达叶子结点，继续判断是否找到了最小总费用
    {
    
        if(Min>sum)   //没有找到最小总费用
        {
    
            Min=sum;   //更新最小总费用
            return;
        }
    }
    for(int i=0;i<n;i++)   //为第工作t安排人
    {
    
        if(!book[i])   //第i个人还没有被安排工作
        {
    
            book[i]=1;   //将工作t分配给第i个人
            sum+=pay[t][i];   //更新总费用
            if(sum<Min)   //如果当前得到的sum小于最小值，就向下搜索子树；否则剪枝
                dfs(t+1);
            book[i]=0;   //没有得到比Min更小的和，回溯
            sum-=pay[t][i];
        }
    }

}

int main()
{
    
    cin>>n;
    for(int i=0;i<n;i++)
    {
    
        for(int j=0;j<n;j++)
        {
    
            cin>>pay[i][j];
        }
        book[i]=0;
    }
    dfs(0);
    cout<<Min<<endl;
    return 0;
}

运行结果

本文链接：https://blog.csdn.net/m0_46308522/article/details/110421351

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c语言求最大公约数和最小公倍数_最大公因数和最小公倍数求法之我见-程序员宅基地

文章浏览阅读1.3k次。随着课程改革的不断推进，老师们逐渐认识到，教材仅仅是课程的一种重要载体，而不是课程的全部。任何课程实施，都需要和开发大量的课程资源。下面就和大家谈一谈除了教材资源，怎样用“数学眼光”来搜索教学资源的。众所周知，最大公因数和最小公倍数有着广泛的应用，特别是在分数四则运算中，更是不可缺失。所以求最大公因数和最小公倍数是小学高年级数学教学的重点，也是难点。下面列举两个数的最大公因数和最小公倍数..._用c语言求24和36的最大公倍数

算法之“鱼龙混杂”-3-程序员宅基地

文章浏览阅读45次。鱼龙混杂：有两个有序（按从小到大排序）数组，现在将数组1添加到数组2，要求数组2只包含数组1中所有值不相同的数据元素！算法思路：先将数组1不相同的元素值添加到数组2，然后再对数组2进行排序！@^_^@using System;using System.Collections.Generic;namespace run{ class Program ...

找不到MSVCP140D.dll-程序员宅基地

文章浏览阅读337次。最近遇到个恶心的问题：发布的Release版本在开发及测试电脑运行OK，但在客户电脑运行报错如下：于是请教大佬解决方案：大佬说可能是因为依赖库中有DEBUG版本的库，并指向了Dependency walker，用此软件可以查看依赖关系；果然使用后发现其中jsoncpp的库依赖有问题：Release版本依赖于Debug版本，所以需要重新编译一个JSONCPP的Release版本库；以下是引用网友编译jsoncpp Release版本库的方法：编译Jsoncpp Release版本...

CentOS之SSH安装与配置-程序员宅基地

文章浏览阅读84次。SSH 为 Secure Shell 的缩写，由 IETF 的网络工作小组（Network Working Group）所制定；SSH 为建立在应用层和传输层基础上的安全协议。传统的网络服务程序，如FTP、POP和Telnet其本质上都是不安全的；因为它们在网络上用明文传送数据、用户帐号和用户口令，很容易受到中间人（man-in-the-middle）攻击方式的攻击。就是存在另一个人或者一台机..._centos安装和配置ssh

cocos creator 龙骨黑边问题解决_cocoscreator 骨骼动画去掉黑边-程序员宅基地

文章浏览阅读1k次。1、龙骨纹理中将预乘勾选2、龙骨组件中将也将预乘勾选龙骨的黑边也就解决了_cocoscreator 骨骼动画去掉黑边

el-table 点击当前行点亮单选按钮基本配置_el-table 单选和点击行单选-程序员宅基地

文章浏览阅读394次。current-change="handleSelectionChange"　　//单选方法，返回选中的表格行。higlight-current-row　　　// element-ui提供的单选方法，可以使当前选中行高亮。handleSelectionChange的方法使用this.radio = row.id来选中单选按钮。:label的绑定属性为:label="scope.row.id"，采用每条项目唯一的标识值。@row-click="chooseone"：单击数据行。_el-table 单选和点击行单选

随便推点

什么是React？-程序员宅基地

文章浏览阅读7.8k次，点赞8次，收藏46次。一、React简介1、React是Facebook开发的一款JS库。2、React一般被用来作为MVC中的V层，它不依赖其他任何的库，因此开发中，可以与任何其他的库集成使用，包括Jquery、Backbone等。3、它可以在浏览器端运行，也可以通过nodejs在服务端渲染。4、React的思想非常独特，性能出众，可以写出重复代码少，逻辑清晰的前端代码。5、React的语法是jsx，通过使用这种语法，可以在react代码中直接混合使用js和html来编写代码，这样代码的逻辑就非常清晰，当然_react

ASEMI整流桥MB10S和MB10F详细对比，哪个比较好？_mb10s与mb10f区别-程序员宅基地

文章浏览阅读2.8k次。编辑-ZMB10F是在MB10S系列基础上根据用户需求开发生产的新型号。从参数功能上看，MB10F就像是瘦身成功的MB10S，那么哪个比较好？ASEMI整流桥MB10S和MB10F详细对比：整流桥MB10S和MB10F的电气参数相同：正向电流（Io）为1A，反向电压为1000V，正向电压（VF）为1.0V，采用GPP芯片材料，其中有4个芯片，芯片尺寸为46MIL，其浪涌电流Ifsm为30A，漏电流（Ir）为5uA，工作温度为-40~+150℃，恢复时间（Trr）为500ns，有4条引线在里面_mb10s与mb10f区别

常用GUI库列表-程序员宅基地

文章浏览阅读1.1k次。FreeToolkits (includingboth Free(in theGNU sense) and no-cost ones)C/C++oriented(unlessexplicit stated with "C API", all toolkits inthis table provide APIs in C++) NameCommentslicenseUnix X11+Unix X11+MotifMS Win 95/9

Pedestrian Alignment Network for Large-scale Person Re-identification（对齐并利用空间变换网络stn）-程序员宅基地

文章浏览阅读758次。年份：1707.ICCV.论文：https://arxiv.org/pdf/1707.00408.pdf代码（.m的代码）：https://github.com/layumi/Pedestrian_Alignment本论文着重对错检和body部分缺失引起的尺度和姿态变化问题研究（如上图），前者可能会使检测得到的图像含有过多的背景，后者则是局部缺失，由此产生的misa lignment对rei..._pedestrian alignment network for large-scale person re-identification

vue【封装 Vue.js 组件库】_vue封装js库-程序员宅基地

文章浏览阅读237次。一、组件库有哪些element-iu iview CDD （Component-Driven Development）自下而上从组件级别开始，到页面级别结束 CDD 的好处组件在最大程度被重用并行开发可视化测试二、组件库开发流程1、处理组件的边界情况$root 小型应用中可以在 vue 根实例里存储共享数据，组件中可以通过 $root 访问根实例 $parent / $children $parent $childre..._vue封装js库

php 数据处理：数组根据某字段进行分组_php 按某个字段分组-程序员宅基地

文章浏览阅读1.6w次。这种数据分组操作比较常用，记录一下，可以直接复制使用 /** * @description:根据数据 * @param {dataArr:需要分组的数据；keyStr:分组依据} * @return: */ protected function dataGroup(array $dataArr,string $keyStr) :..._php 按某个字段分组