工作分配问题

男娘i 2022-04-24 11:00 138阅读 0赞

### 工作分配问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。

Output

将计算出的最小总费用输出。

Sample Input

3
    10 2 3
    2 3 4
    3 4 5

Sample Output

9

#include <iostream>
    using namespace std;
    #define inf 0x3f3f3f3f
    
    int n, ans;
    int c[25][25];
    int vis[25];
    
    void dfs(int i, int sum)//i是行号
    {
    	if (sum > ans) //剪枝
    		return;
    	if (i == n + 1 && sum < ans)
    	{
    		ans = sum;
    		return;
    	}
    	for (int j = 1; j <= n; j++)
    	{
    		if (!vis[j])//遍历第i行 没有被遍历过列号j 的元素
    		{
    			vis[j] = 1;
    			dfs(i + 1, sum + c[i][j]);
    			vis[j] = 0;
    		}
    	}
    }
    int main()
    {
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= n; j++)
    			cin >> c[i][j];
    	ans = inf;
    	dfs(1, 0);
    	cout << ans << endl;
    	return 0;
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读

相关动态内存分配是如何工作的

动态内存分配是指在程序运行期间根据需要可以动态地分配和释放内存的过程。在动态内存分配中，内存可以根据需要随时分配和释放，这使得程序开发者可以更有效地利用内存，更好地支持程序运行

た入场券/ 2024年03月25日 16:07/ 0 赞/ 35 阅读

相关工作分配问题——算法设计与分析（C实现）

目录一、问题描述二、问题分析三、代码展示四、结果验证 -------------------- 一、问题描述问题描述：设有n件工作分配给n个人。将

秒速五厘米/ 2024年03月17日 11:11/ 0 赞/ 39 阅读

相关 PTA--工作分配问题

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。输入格式:

你的名字/ 2022年12月27日 12:36/ 0 赞/ 140 阅读

相关任务分配问题需求

一需求一个医药代表，每天会给它安排一些工作任务，领导会让他每天做一定次数的医院拜访，一定次数的商业拜访，一定次数的药房拜访，每天拜访的总次数不能超过8次。医药代表

太过爱你忘了你带给我的痛/ 2022年09月14日 09:41/ 0 赞/ 224 阅读

相关任务分配问题

<table style="max-width:100%;border-spacing:0px;width:1669px;margin-bottom:20px;backgrou

た入场券/ 2022年05月27日 07:42/ 0 赞/ 177 阅读

相关工作分配问题

工作分配问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n件工作分配给n个人

男娘i/ 2022年04月24日 11:00/ 0 赞/ 139 阅读

相关任务分配问题

问题描述：假设有n个任务需要分配给n个人执行，每个人只执行一个任务，每个任务只由一个人执行。第i个人执行第j个任务的成本是Cij(1<=i,j<=n), 求解初最小成本

柔光的暖阳◎/ 2022年04月16日 05:07/ 0 赞/ 214 阅读

相关 1776 工作分配问题

工作分配问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n件工作分配给n个人

淩亂°似流年/ 2022年02月15日 06:24/ 0 赞/ 128 阅读

相关工作分配问题

工作分配问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

你的名字/ 2022年02月15日 04:59/ 0 赞/ 158 阅读

相关委派模式——分配工作任务

一代码位置 [https://gitee.com/cakin24/javatest][https_gitee.com_cakin24_javatest] 二代码 1

骑猪看日落/ 2021年07月24日 16:34/ 0 赞/ 309 阅读