精华内容
下载资源
问答
  • 某厂根据计划安排,拟将n台相同的设备分配给m个车间,各车间获得这种设备后,可以为国家提供盈利Ci j(i台设备提供给j号车间将得到的利润,1≤i≤n,1≤j≤m) 。问如何分配,才使国家得到最大的盈利?
  • 动态规划 资源分配问题 代码超详细注释!!!

    千次阅读 多人点赞 2021-01-07 20:27:21
    #include<iostream>...//资源最大利润分配表 float q[100],f[100],temp[100];//利润表 当前最大收益 正在计算的最大收益 printf("输入工程数m:"); scanf("%d",&m); printf("输入总资源数n:...

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    #include<iostream>
    
    using namespace std;
    
    int main()
    {
    	int m,n;// 工程数,资源数, 
        int  a[100][100],gain[100];//不同资源情况下最大利润分配表 项目对应的资源分配表 
    	float  q[100],f[100],temp[100];//利润表  当前最大收益 正在计算的最大收益 
    	printf("输入工程数m:");
    	scanf("%d",&m);
        printf("输入总资源数n:");
    	scanf("%d",&n);
        printf("输入第1个工程获利的利润表:\n");
        for( int j=0;j<= n;j++){
        	//从(0,0)开始,一共八个数据 
    		scanf("%f",&q[j]);
    		f[j]=q[j];//只有一个项目时资源所对应的最大收益即为该项目的最大收益 
    		temp[j]=q[j];// 
    		a[1][j]=j;//只有一个项目情况下 全都分配给当前项目时利润最高 
    	}
    	for(int k=2;k<=m;k++){//依次加入新工程 计算最大利润 
    		printf("输入第%d个工程获利的利润表:\n",k);
        	for(int j=0;j<= n;j++){
        		//从(0,0)开始,一共八个数据  
        		scanf("%f",&q[j]);
            	f[j]=0;// 
           	    a[k][j]=0;//默认不分配资源给新项目 
            }
    	    for(int  j=0 ;j<= n;j++){//进行不同资源情况的计算 
    	    	printf("资源数为%d时:\n",j);
    	    	for( int i=0 ;i<=j;i++){// //分配给新项目的资源数 
    	    	/*
    				分配给新项目i资源的利益+剩余资源分配给其他项目的利益 是否大于 当前所计算的最大利益
    				1.大于 (此时分配方案为最优) 
    					A.记录此时分配给新项目的资源数
    					B.记录当有j个资源时 最大利益值
    				2.不大于 (方案不是最优 不做更新) 
    			*/ 
    	    		if (temp[j-i] + q[i] > f[j]){
    					f[j] = temp[j-i]+q[i]; 
    					a[k][j]=i; 
                    }
    				printf("%3.2f  ",q[i]+temp[j-i]);		
    			}	
    			printf("\n");
    		}
    	 	printf("当前最大利润表如下:\n");
            for(int j=0;j<= n;j++){
            	temp[j]=f[j];//记录已算的项目资源分配利益总表 
            	printf("f[%d]:%3.2f  ",j,f[j]);
    		}
    		printf("\n"); 
        }
        int rest=n;//总共rest个资源 剩余未分配资源数
    	for(int i=m;i>=1;i--){//记录每个项目的资源分配情况 
            gain[i] = a[i][rest];//i项目当整体取得最大利益时分配的资源数 
            rest = rest - gain[i];//剩余的资源数 
        }
        for(int i=1;i<=m;i++)
            printf("第%d个项目投资%d万元\n",i,gain[i]);
    	printf("总利润为%3.2f\n",f[n]);
    }
    
    展开全文
  • 某厂根据计划安排,拟将n台相同的设备分配给m个车间,各车间获得这种设备后,可以为国家提供盈利Ci j(i台设备提供给j号车间将得到的利润,1≤i≤n,1≤j≤m) 。问如何分配,才使国家得到最大的盈利?
  • 动态规划 资源分配问题

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

    资源分配问题是考虑如何把有限分配给若干个工程的问题。参考《算法设计与分析》

    下面直接贴代码:

    //为了和书上的内容一致,我的变量名、变量所代表的意思和书上的几本一致
    #include<iostream>
    #include<vector>
    #define  M 8  //可分配资源份额
    #define  N 3  //工程项目个数 
    using namespace std;
                  //定义算法所需的数据结构
    int G[N][M+1]={              //声明,赋值开辟了空间是可以的
    {0,4,26,40,45,50,51,52,53},
    {0,5,15,40,60,70,73,74,75},
    {0,5,15,40,80,90,95,98,100}
    };
    int optg;     //最优分配时所得的总利润
    int optq[N];  //最优分配时各项工程所得的份额


                  //算法的工作单元
     
    int f[N][M+1];//前i项工程分配不同份额资源是可得到的最大利润
    int d[N][M+1];//是使f[i][x]最大时,第i项工程分配的份额
    int g[N];     //只分配前i项工程时,可得到的最大利润
    int q[N];     //只分配前i项工程时,第i项工程最优分配份额
    int optx;     //最优分配时的资源最优分配份额
    int kk;        //最优分配时的工程项目的最大编号


    void main(void)
    {
    //初始化
    /*
    G[N][M+1]={
    {0,4,26,40,45,50,51,52,53},             //这样是错的,这样赋值没有开辟空间,需要new函数才可以
    {0,5,15,40,60,70,73,74,75},             // 
    {0,5,15,40,80,90,95,98,100}             //
    };
    */

        //第一阶段
    for (int v=0;v<M+1;v++)
    {
    f[0][v]=G[0][v];
    d[0][v]=v;
    }
    //其他阶段
    int vv;
        int b_num;
    for(int k=1;k<N;k++)
    {
    for(int i=0;i<M+1;i++)
    {
    int MAX_total=0;
    for(int j=0;j<=i; j++)
    {
                  vv=G[k][j]+f[k-1][i-j];
                  if(vv>MAX_total)
     {
     MAX_total=vv;
     b_num=j;
     }
    }
    f[k][i]=MAX_total;
    d[k][i]=b_num;
    }
    int uu=0;
    int a_num;
            for(int l=0;l<M+1;l++)
    {
                if(f[k][l]>uu)
    {
    uu=f[k][l];
    a_num=l;
    }
    }
    g[k]=uu;
            q[k]=a_num;
    }
    //第一种细节处理方法 ,浪费空间
    /*
    int c_num=0;
    int f_num;
    for(int ll=0;ll<N;ll++)
    {
           if(c_num<g[ll])
      {
      c_num=g[ll]; 
      f_num=ll;
      }
    }
    optg=c_num;
    kk=f_num;
    optx=q[f_num];
    */
    //第二种细节处理方法
    optg=g[0]; 
    optx=q[0];
    kk=0;
    for(int i=1;i<N;i++)
    {
    if(optg<g[i])
    {
    optg=g[i];
    optx=q[i];
    kk=i;
    }
    }
        
        if(kk<N-1)///为什么要加这一步,这就是思路的缜密
    {
    for(int i=kk+1;i<N;i++)
    {
    optq[i]=0;
    }
    }


    for(int u=N-1; u>=0; u--)
    {
            optq[u]=d[u][optx];
    optx=optx-optq[u];
    }
    for(int r=0;r<N;r++)
    {
    cout<<optq[r]<<endl;
    }
    cout<<"最高利润为:"<<optg<<endl;

    }

    为了更好的理解资源分配问题,特推荐http://blog.csdn.net/sophie_wise8/article/details/6142488 这篇博客和《算法设计与分析》143页

    有资金4万元,投资A、B、C三个项目,每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益(万吨)和投入资金(万元)的关系见下表:

          项目

    投入资金

    A

    B

    C

    1万元

    15万吨

    13万吨

    11万吨

    2万元

    28万吨

    29万吨

    30万吨

    3万元

    40万吨

    43万吨

    45万吨

    4万元

    51万吨

    55万吨

    58万吨

     求对三个项目的最优投资分配,使总投资效益最大。

    阶段k:每投资一个项目作为一个阶段;

    状态变量xk:投资第k个项目前的资金数;

    决策变量dk:第k个项目的投资;

    决策允许集合:0dkxk

    状态转移方程:xk+1=xk-dk

    阶段指标:vk(xk,dk)见表中所示;

    递推方程:fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}

    终端条件:f4(x4)=0

    k=4f4(x4)=0

    k=30d3x3x4=x3-d3

    x3

    D3(x3)

    x4

    v3(x3,d3)

    v3(x3,d3)+f4(x4)

    f3(x3)

    d3*

    0

    0

    0

    0

    0+0=0

    0

    0

    1

    0

    1

    0

    0+0=0

    11

    1

    1

    0

    11

    11+0=11*

    2

    0

    2

    0

    0+0=0

    30

    2

    1

    1

    11

    11+0=11

    2

    0

    30

    30+0=30*

    3

    0

    3

    0

    0+0=0

    45

    3

    1

    2

    11

    11+0=11

    2

    1

    30

    30+0=30

    3

    0

    45

    45+0=45*

    4

    0

    4

    0

    0+0=0

    58

    4

    1

    3

    11

    11+0=11

    2

    2

    30

    30+0=30

    3

    1

    45

    45+0=45

    4

    0

    58

    58+0=58*

     

    k=20d2x2x3=x2-d2

    x2

    D2(x2)

    x3

    v2(x2,d2)

    v2(x2,d2)+f3(x3)

    f2(x2)

    d2*

    0

    0

    0

    0

    0+0=0

    0

    0

    1

    0

    1

    0

    0+11=11

    13

    1

    1

    0

    13

    13+0=13*

    2

    0

    2

    0

    0+30=30*

    30

    0

    1

    1

    13

    13+11=24

    2

    0

    29

    29+0=29

    3

    0

    3

    0

    0+45=45*

    45

    0

    1

    2

    13

    13+30=43

    2

    1

    29

    29+11=40

    3

    0

    43

    43+0=43

    4

    0

    4

    0

    0+58=58

    59

    2

    1

    3

    13

    13+45=58

    2

    2

    29

    29+30=59*

    3

    1

    43

    43+11=54

    4

    0

    55

    55+0=55

     

    k=10d1x1x2=x1-d1

    x1

    D1(x1)

    x2

    v1(x1,d1)

    v1(x1,d1)+f2(x2)

    f1(x1)

    d1*

    4

    0

    4

    0

    0+59=59

    60

    1

    1

    3

    15

    15+45=60*

    2

    2

    28

    28+30=58

    3

    1

    40

    40+13=53

    4

    0

    51

    51+0=51

    最优解为x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0

    即项目A投资1万元,项目B投资0万元,项目C投资3万元,最大效益为60万吨。




    展开全文
  • 运行环境为:VS2017 有问题欢迎私信 ...资源分配问题 实验要求 资源总数为,工程个数为。给每项工程投入的资源不同,所获得的利润也不同。要求把总数为的资源,分配给个工程,以获得最大利润的分配方案。
  • 动态规划_求解资源分配_实验报告动态规划_求解资源分配_实验报告
  • 动态规划--资源分配问题

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

    问题描述:

    资源分配问题是将数量一定的一种或若干种资源(原木料、资金、设备或劳动力等)合理地分配给若干个使用者,使总收益最大。

    例如,某公司有3个商店A、B、C,拟将新招聘的5名员工分配给这3个商店,各商店得到新员工后每年的赢利情况如表所示,求分配给各商各多少员工才能使公司的赢利最大?

     

    解析:

    其实就是完全背包的变形

    用dp[i][j]表示为前i个商店共分配j个人时盈利的最大值,状态转移方程如下(k表示为i商店分配的人数):

    dp[i][j] = max(dp[i][j], dp[i-1][j-k] + c[i][k])

    求解过程如下(括号内红字表示选的人数,画框的表示倒退求解的过程):

    具体代码:

    #include <iostream>
    #include <cstdio>
    #include <vector>
    
    using namespace std;
    const int MAX = 30;
    
    vector<int> ans;
    
    int c[MAX][MAX], dp[MAX][MAX]; // dp[i][j]表示前i个车间共分配j个人
    int pnum[MAX][MAX];
    int n, m;
    
    int DP_source()
    {
        // 初始化
        for(int i = 0; i <= n; i++)
            dp[i][0] = 0;
    
        for(int i = 0; i <= m; i++)
            dp[0][i] = 0;
    
    
        int sel_num = 0; // 记录第i个车间分配j人时应分配的人数
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                sel_num = 0;
    
                for(int k = 0; k <= j; k++) // 枚举当前车间分配k人时的最大值
                {
                    if(dp[i][j] < dp[i - 1][j - k] + c[i][k]) // 更新答案
                    {
                        dp[i][j] = dp[i - 1][j - k] + c[i][k];
                        sel_num = k;
                    }
                }
    
                // 循环结束后找到为前i个车间共分配j人时第i个车间应分配的人数
    
                pnum[i][j] = sel_num;
            }
        }
    
        return dp[n][m];
    
    }
    
    void print_allocate() // 输出每个车间应分配的人数
    {
        int r, s;
        s = pnum[n][m]; // 最后一个车间应该选择的人数
        r = m - s; // 剩余人数
        for(int i = n; i >= 1; i--)
        {
            printf("%d 商店分配 %d 人\n", i, s);
    
            s = pnum[i- 1][r];
            r -= s;
        }
    }
    
    int main()
    {
    
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j ++)
            scanf("%d", &c[i][j]);
    
        printf("max = %d\n", DP_source());
        print_allocate();
    
    
        return 0;
    }
    
    /*
    3 5
    3 7 9 12 13
    5 10 11 11 11
    4 6 11 12 12
    */
    

     

    展开全文
  • 动态规划法求解资源分配问题

    热门讨论 2012-07-07 22:49:53
    实验名称:用动态规划法求解资源分配问题 (验证型实验) 实验目标: (1)掌握用动态规划方法求解实际问题的基本思路。 (2)进一步理解动态规划方法的实质,巩固设计动态规划算法的基本步骤。 实验任务: (1)...
  • 3 3 动态规划求解资源分配 实验目标 掌握用动态规划方法求解实际问题的基本思路 进一步理解动态规划方法的实质巩固设计动态规划算法的基本步骤 实验任务 设计动态规划算法求解资源分配问题给出算法的非形式描述 在 ...
  • 动态规划资源分配

    千次阅读 2019-12-17 17:29:32
    概要 动态规划的决策不是线性的而是全面考虑到各种不同情况分别进行决策,最后通过多阶段决策逐步找出问题最优解。...例1、资源分配问题 现有7万元需要投资到A,B,C三个项目,利润表如下图。求总利润分配...

    概要

    动态规划的决策不是线性的而是全面考虑到各种不同情况分别进行决策,最后通过多阶段决策逐步找出问题最优解。而当前决策也会依赖于上一阶段的决策,此时便会发生状态的转移。动态规划算法可以说是一种“聪明的蛮力法”,因为动态规划是会考虑到每一种可能,而聪明的地方是相对于蛮力法,它去掉了很多没必要的运算。

     

     例1、资源分配问题

    现有7万元需要投资到A,B,C三个项目,利润表如下图。求总利润分配最大的资源分配方案

     1234567
    A0.110.130.150.210.240.300.35
    B0.120.160.210.230.250.240.34
    C0.080.120.200.240.260.300.35

     

    #include <iostream>
    using namespace std;
    int main(){
    	
    	double invest[3][8]={//投资表,记录了A,B,C三个投资的利润率信息,预留多一个位置,invest[i][j]中i表示项目,j表示金额 
    						{0,0.11,0.13,0.15,0.21,0.24,0.30,0.36},
    						{0,0.12,0.16,0.21,0.23,0.25,0.24,0.34},
    						{0,0.08,0.12,0.20,0.24,0.26,0.30,0.35}
    						};
    	double max[8],temp[8]={0},gain[8]={0};//max记录的是优策略下的投资利润率,gain记录的是当前投资金额可得的最大利润
    	//temp记录的是上一次决策中可以获得的最大利润 
    	for(int i=0;i<8;i++){//初始化,当只有A投资可选时,最优投资策略便是全部投资A 
    		max[i]=invest[0][i];
    	}
    	
    	for(int i=0;i<8;i++){//初始化,当只有A投资可选时,可以得到的最大利润
    		gain[i]=invest[0][i]*i;
    	}	 
    	
    	for(int i=1;i<3;i++){//控制投资项目 
    		for(int j=1;j<8;j++){//控制投资金额,j即为当前的投资金额
    			for(int k=0;k<j;k++){//k表示投资给上一个最优决策的金额, j-k表示把剩余的资金投资给新添加的那个项目 
    				temp[j]=max[k]*k+invest[i][j-k]*(j-k); 
    				if(gain[j]<temp[j]){
    					gain[j]=temp[j];
    					max[j]=gain[j]/j;
    				}				
    			}
    		}
    	}
    	//输出 
    	cout<<"最大投资利润率为:"; 
    	for(int i=1;i<8;i++){
    		cout<<max[i]<<" ";
    	} 
    	cout<<endl<<"最大利润为:";
    	for(int i=1;i<8;i++){
    		cout<<gain[i]<<" ";
    	} 	
    }

     

    展开全文
  • 动态规划代码

    2018-10-16 09:31:01
    动态规划的python代码,可用于动态规划的编写,在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。
  • 动态规划法求解资源分配问题

    千次阅读 2020-03-28 20:16:23
    资源分配问题是将数量一定的一种或若干种资源(原材料、资金、设备或劳动力等),合理地分配给若干使用者,使总收益最大。 例如,某公司有3个商店A、B、C,拟将新招聘的5名员工分配给这3个商店,各商店得到新员工后...
  • 上一篇文章写了动态规划求解0-1背包问题,这里做一道资源分配问题强化理解,顺便分析一下动态规划算法的优化问题。 问题描述:某厂根据计划安排,拟将n台相同的设备分配给m个车间,各车间获得这种设备后,可以为...
  • 42、动态规划-资源分配问题

    千次阅读 2019-08-30 13:42:00
    import random as rd import matplotlib.pyplot as plt import functools import math import copy import time from pyscipopt import ...#资源分配问题,例如n台机器分给m个工厂 def sub_LL_print(L, digit): s...
  • 动态规划资源离散分配(python代码) 问题:资源离散分配问题 (问题来自中国大学MOOC-华中科技大学-运筹学) 动态规划的思想在于把一个大问题化成一些同类型的子问题,然后逐个求解。从边界条件开始递推,每一个子...
  • 资源分配动态规划

    千次阅读 2019-08-06 18:14:49
    资源分配(链接) 资源分配问题就是将一定数量的一种或若干种资源(原材料、资金、设备等)合理分配给若干使用者,使得资源分配后总结果最优。一种资源的分配问题称为一维资源分配问题,两种资源的分配问题称为二维...
  • 如题,在写论文,求一个多维资源分配 动态规划的python代码,跪求。
  • 资源分配问题:某厂根据计划安排,拟将n台相同的设备分配给m个车间,各车间获得这种设备后,可以为国家提供盈利Ci j(i台设备提供给j号车间将得到的利润,1≤i≤n,1≤j≤m)。问如何分配,才使国家得到最大的盈利? ...
  • 动态规划应用举例---资源分配问题

    千次阅读 2018-12-09 22:20:00
    一维资源分配问题 二维资源分配问题 固定资金分配问题 转载于:...
  • 问题描述:把4个份额的资源分配给3个工程,给定利润表如下表所示,写出资源的最优分配方案的求解过程。
  • 一、资源分配问题 二、关键路径问题 求得是两点之间最长的路径,不是最短的路径,因为要知道工程多少天 边就是项目,结点就是开始或者结束 关键活动就是边 算法定义: 需要遍历两次:从前向后和从后向前 从前向...
  • 动态规划研究的问题 内容 动态规划思想 问题举例一:最短路问题 问题举例二:资源分配问题 例 5.1.2 离散变量的资源分配问题 多阶段决策问题 动态规划的最优子结构性质 动态规划的子问题重叠性质 前向优化 后向优化 ...
  • 实验名称:用动态规划法求解资源分配问题 (验证型实验) 实验目标: (1)掌握用动态规划方法求解实际问题的基本思路。 (2)进一步理解动态规划方法的实质,巩固设计动态规划算法的基本步骤。 实验任务: (1)...
  • [算法]动态规划解决投资分配问题

    千次阅读 2019-04-30 11:25:41
    * 第八章 动态规划 * 投资分配问题 * * */ #include <iostream> using namespace std; void DynamicInvest() { int a[100][100];// a[i][j] 前i个项目投资j万元 给第i个项目投资a[i][j]万元时收益最大...
  • 资源分配c++代码

    2018-10-31 11:19:09
    设有资源a,分配给几个项目。代码里有注释,自己看下就行。具体不介绍了
  • 动态规划求解资源分配 动态规划求解资源分配 实验目标 实验目标 1 1 掌握用动态规划方法求解实际问题的基本思路 掌握用动态规划方法求解实际问题的基本思路 2 2 进一步理解动态规划方法的实质巩固设计动态规划算法的...
  • 数学建模中非线性规划问题的原理分析及MATLAB求解过程
  • 动态规划求解资源分配 实验目标 1掌握用动态规划方法求解实际问题的基本思路 2进一步理解动态规划方法的实质巩固设计动态规划算法的基本步骤 实验任务 1设计动态规划算法求解资源分配问题给出算法的非形式描述 2 在...
  • 动态规划资源分配问题

    万次阅读 2011-01-15 17:02:00
     项目投入资金ABC1万元15万吨13万吨11万吨2万元28万吨29万吨30万吨3万元40万吨43万吨45万吨4万元51万吨55万吨58万吨求对三个项目的最优投资分配,使总投资效益最大。阶段k:每投资一个项目作为一个阶段;状态变量xk...
  • 动态规划求解资源分配实验报告.doc

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,461
精华内容 14,984
关键字:

动态规划资源分配