精华内容
下载资源
问答
  • 任务分配问题

    千次阅读 2018-11-17 11:46:25
    问题描述: 假设有n个任务需要分配给n个人执行,每个人只执行一个任务,每个任务只由一个人执行。第i个人执行第j个任务的成本...任务分配问题转化为,在矩阵中的每一行选取一个元素,这些元素分别属于不同的列。用...

    问题描述:

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

    蛮力法:

    算法描述:用矩阵表示任务分配问题,矩阵元素Cij(1<=i,j<=n)表示人员i执行任务j的成本。任务分配问题转化为,在矩阵中的每一行选取一个元素,这些元素分别属于不同的列。用一个n元组(j1,j2,...,jn)表示一个可能解,其中ji表示第i行中选择的列号。用暴力法解决此问题则可表示成,生成一个n元组的全排列,遍历输出最小的成本代价即可。 

    代码:

    #include<stdio.h>
    #include<iostream>
    #include<stdlib.h>
    #include<math.h>
    #include<algorithm>
    #define MAX 99999
    using namespace std;
    int main()
    {
        int num,c[10][10],i,j,temp[10],minCost=MAX,cost=0;
        cout<<"输入任务个数:\n";
        cin>>num;
        cout<<"输入成本矩阵\n";
        for(i=1;i<=num;i++){            //输入成本的矩阵值
            for(j=1;j<=num;j++)
                cin>>c[i][j];
            temp[i]=i;                  //设置全排列辅助数组,默认升序
        }
        do{                             //利用next_permutation函数依次求出数组的全排列
            cost=0;
            for(i=1;i<=num;i++)
                cost+=c[i][temp[i]];
            if(cost<minCost)minCost=cost;           //记录最小代价
        }while(next_permutation(temp+1,temp+1+num));
        cout<<"最小成本:\n"<<minCost;
        return 0;
    }
    

    算法分析: 一个n元组的全排列的个数为n!故时间复杂度为O(n!).

    还发现一个不错的文章http://www.cnblogs.com/dwdxdy/p/3261742.html

    展开全文
  • 工作分配问题

    千次阅读 2017-11-30 17:43:01
    对于工作分配问题,可以采用排列树的递归算法进行求解。要将n个工作分配给n个人,并要求费用最小,就需要依次计算出不同分配情况下的费用,到达叶节点之后再进行比较,即在遍历排列树的过程中是没有限界函数和约束

    问题描述:

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

    算法思路:

    对于工作分配问题,可以采用排列树的递归算法进行求解。要将n个工作分配给n个人,并要求费用最小,就需要依次计算出不同分配情况下的费用,到达叶节点之后再进行比较,即在遍历排列树的过程中是没有限界函数和约束函数的。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    int n,bestx=0,b=0;
    intc[1024][1024],x[1024],bx[1024];
    void backtrace(int t){
        if(t>n){
           if(b <bestx){
              bestx=b;//如果所得时间比之前的都小的话,就进行更新
              for(inti=1;i<=n;i++)
                bx[i]=x[i];
           }
            
        }else{
           for(int i=t;i<=n;i++){//这是排列树 ,需要有x数组进行交换
               b += c[t][x[i]];//t表示的是深度,也就是工作序号,i表示分配给的人
                swap(x[i],x[t]);
               backtrace(t+1);
               swap(x[i],x[t]);
               b -= c[t][x[i]];//回溯         
           }
        }
    }
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++)
            cin>>c[i][j];
            bestx+=c[i][1];
        }
        for(int i=1 ;i<=n;i++)//对x数组进行顺序初始化
          x[i] = i;
          backtrace(1);
         cout<<bestx<<endl;
          for(int i=1;i<=n;i++)
            cout<<bx[i]<<" ";
        return 0;
    }


    展开全文
  • 资源分配问题

    千次阅读 多人点赞 2020-07-20 15:14:18
    某工业生产部门根据国家计划的安排,拟将某种高效率的5台机器,分配给所属的3个工厂A,B,C, 各工厂在获得这种机器后,可以为国家盈利的情况如表1所示。问:这5台机器如何分配给各工厂,才能使得国家利益最大? ...

    资源分配问题

      大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客

    本文原创为亓官劼,请大家支持原创,部分平台一直在盗取博主的文章!!!

    博主目前仅在CSDN中写博客,唯一博客更新的地址为:亓官劼的博客


    在这里插入图片描述

    题目

    某工业生产部门根据国家计划的安排,拟将某种高效率的5台机器,分配给所属的3个工厂A,B,C, 各工厂在获得这种机器后,可以为国家盈利的情况如表1所示。问:这5台机器如何分配给各工厂,才能使得国家利益最大?

    利益表:

    S A B C
    0 0 0 0
    1 3 5 4
    2 8 10 6
    3 9 11 11
    4 12 11 12
    5 13 11 12

    输出为:

    A B C最优分配机器数依次为2 2  1
    最大盈利值为22
    

    题解

    #include <iostream>
    #include <vector>
    using namespace std;
    int main(){
        int a[6][3];
        for (int i = 0; i < 6; ++i) {
            for (int j = 0; j < 3; ++j) {
                cin>>a[i][j];
            }
        }
        int i,j,a_num,b_num,c_num,sum,maxm;
        maxm = 0;
        for(i=0;i<=5;i++)
        {
            for(j=0;j<=5-i;j++)
            {
                sum=a[i][0]+a[j][1]+a[5-i-j][2];
                if(sum>maxm)
                {
                    maxm=sum;
                    a_num=i;
                    b_num=j;
                    c_num=5-i-j;
                }
            }
        }
        cout<<"A B C最优分配机器数依次为"<<a_num<<" "<<b_num<<" "<<" "<<c_num<<endl;
        cout<<"最大盈利值为"<<maxm;
        return 0;
    }
    
    展开全文
  • 任务分配问题算法

    千次阅读 2020-04-15 15:28:47
    任务分配问题算法代码简化至34行 问题:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。 源代码: import ...

    任务分配问题算法代码简化至34行
    问题:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。

    源代码:

    import java.util.Arrays;
    public class Assignment {
    	static int arr[][]= {{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};
    	static int min=arr[0][0]+arr[1][0]+arr[2][0]+arr[3][0];
    	public static void main(String args[]) {
    		int solve[]= {0,1,2,3};
    		assignment(solve,0);		
    	}
    	static void assignment(int solve[],int i) {
    		if(i==arr.length) {
    			int temp=check(solve);
    			if(temp<min) {
    				min=temp;
    				System.out.println("Min: "+min+"  Solve: "+Arrays.toString(solve));
    			}			
    		}							
    		for(int j=i;j<arr.length;j++) {
    			swap(solve,i,j);
    			assignment(solve,i+1);
    			swap(solve,i,j);
    		}	
    	}
    	static int check(int solve[]) {
    		int sum=0;
    		for(int i=0;i<solve.length;i++)
    			sum+=arr[i][solve[i]];
    		return sum;
    	}
    	static void swap(int solve[],int i,int j) {
    		int t=solve[i];
    		solve[i]=solve[j];
    		solve[j]=t;
    	}
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 最优分配问题——拍卖算法

    千次阅读 2020-06-04 22:30:54
    分配问题 广泛存在于生产和生活中。例如为一组工作人员分配任务,或者为作战小组分配进攻目标等等。在分配过程中,精明的分配者一定会实现某个目的,例如让每个工作人员充分发挥专长,最高质量地完成任务;或者为每...
  • ACM 任务分配问题

    千次阅读 2018-07-19 08:52:50
    任务分配问题 Problem Description 现有 n 件任务和无限多台的机器,任务可以在机器上得到处理。每件任务的开始时间为 si,完成时间为 ei,[si, ei]为处理任务的时间范围。2 个任务重叠是指 2 个任务的时间范围有...
  • 最优化资源分配问题

    千次阅读 2018-10-28 12:33:26
    最优化资源分配问题 问题提出:现有三个发电厂A,B,C其生产成本和最大发电度数分别如下: 发电厂 生产成本T 最大发电度数 A P^2.2 1千万度 B 2p^1.8 1.5千万度 C 0.8p^2.0 1.8千万度 问:全年总发电量不少于3千万度,...
  • (Java实现) 工作分配问题

    万次阅读 多人点赞 2019-06-02 08:34:52
    工作分配问题 时间限制: 1 Sec 内存限制: 128 MB [提交][状态][讨论版] 题目描述 设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法,计算最佳工作分配方案,为每一个人都分配1 ...
  • 资源分配问题是将数量一定的一种或若干种资源(原木料、资金、设备或劳动力等)合理地分配给若干个使用者,使总收益最大。 例如,某公司有3个商店A、B、C,拟将新招聘的5名员工分配给这3个商店,各商店得到新员工后每年...
  • 蛮力法解决任务分配问题

    千次阅读 2018-10-08 10:54:17
    问题描述:假设有n个任务需要分配给n个人执行,每个任务只分配给一个人,每个人只分配一个任务,且第j个任务分配给第i个人的成本是C[i, j](1≤i , j≤n),任务分配问题要求找出总成本最小的分配方案。 可以用一...
  • 最佳调度问题与工作分配问题乍一看像是两种题目,但实际上这两种问题在有些时候可以用相似的方法来解决(我遇到的这两个题目是用的同一种方法解决的,不确定是否所有的这两类问题方法都能共用),直接上题目了。...
  • 城际网约车订单分配问题及其求解算法问题的定义数学建模用于城际网约出行的智能订单分配算法智能订单分配算法 问题的定义   城际网约车订单分配问题是订单分配问题的一种,它主要是为了解决特定城市之间的个性化...
  • 动态规划法求解资源分配问题

    千次阅读 2020-03-28 20:16:23
    资源分配问题是将数量一定的一种或若干种资源(原材料、资金、设备或劳动力等),合理地分配给若干使用者,使总收益最大。 例如,某公司有3个商店A、B、C,拟将新招聘的5名员工分配给这3个商店,各商店得到新员工后...
  • 工作分配问题(job)

    千次阅读 2019-02-14 17:35:05
    工作分配问题(job) Description 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为c_{ij} 。试设计一个算法,为每一个人都 分配一件不同的工作,并使总费用达到最小。 设计一个算法,对于给定的工作费用...
  • python遗传算法解决分配问题

    千次阅读 2019-08-07 12:18:05
    python遗传算法解决分配问题 import numpy as np import random import matplotlib.pyplot as plt def get_rand(): select = [x for x in range(10)] random.shuffle(select) return select time = np.array...
  • Lingo与资源分配问题

    千次阅读 2018-08-16 16:08:53
    Lingo与一维资源分配问题 代码如下: sets: R/1..6/:z; L/1..3/; c(R,L):x,y; endsets data: X=0 0 0 5 5 4 15 15 26 40 40 40 80 60 45 90 70 50; z=0 1 2 3 4 5; enddata max=@sum(c(i,j):X(i,j)*y(i...
  • 任务分配问题(匈牙利算法)

    千次阅读 2018-10-20 14:30:03
    【算法题】任务分配问题---匈牙利算法 一、问题描述 问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数...
  • 动态规划 资源分配问题

    千次阅读 2016-05-09 14:26:32
    资源分配问题是考虑如何把有限分配给若干个工程的问题。参考《算法设计与分析》 下面直接贴代码: //为了和书上的内容一致,我的变量名、变量所代表的意思和书上的几本一致 #include #include #define M 8 //可...
  • 算法分析之工作分配问题

    千次阅读 2017-03-28 10:36:27
    ACM中的工作分配问题是一个典型的回溯问题,利用回溯思想能很准确地得到问题的解。下面就这个问题好好分析下。 问题描述:  设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法,...
  • 分配问题与匈牙利算法

    万次阅读 2017-01-17 16:13:28
    分配问题与匈牙利算法例1假如你是个玩具工厂的销售经理,你现在有三个销售人员要去不同城市见买家。你的销售人员分别在在奥斯丁,得克萨斯州;波士顿、马里兰州;和芝加哥,伊利诺伊州。你想让他们飞往其他三个城市...
  • 工作分配问题 assignment problem

    千次阅读 2014-09-18 04:07:34
    工作分配问题 assignment problem 有匈牙利算法
  • 工作分配问题 解题报告

    千次阅读 2015-08-13 08:55:44
    工作分配问题 【问题描述】  设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法,为每一个人都分配一件不同的工作,并使总费用达到最小。 【编程任务】  设计一个算法,对于给定...
  • 有趣的概率:赌注分配问题

    千次阅读 2020-06-29 14:48:58
    文章目录简介赌注分配问题求助帕斯卡再来赌一场吧解释: 简介 数学并不是高屋建瓴,其实往往是对来自生活中的常识或者偏见的理论总结。概率就是源自生活中的随机现象。 我个人对德州扑克还是很感兴趣的,比如见第...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 65,278
精华内容 26,111
关键字:

分配问题