首页 > 其他分享 >动态规划法-资源分配问题

动态规划法-资源分配问题

时间:2024-09-02 21:53:03浏览次数:14  
标签:最大 工程 资源分配 int 规划法 动态 分配 利润

动态规划法 - 资源分配问题

问题描述

把4个份额的资源分配给3个工程,给定利润表如下表所示,写出资源的最优分配方案的求解过程。
在这里插入图片描述
4份资源分配给3个工程的利润表

步骤一:求各个阶段不同分配份额时的最大利润及分配份额

目标

我们的目标是找到在给定资源限制下,如何分配资源给不同的工程以获得最大利润。

步骤

  1. 定义子问题:我们定义 fᵢ(x) 为将 x 份资源分配给前 i 个工程时的最大利润,dᵢ(x) 为在 fᵢ(x) 最大时,分配给第 i 个工程的资源份额。
  2. 初始化:对于只有一个工程的情况,我们可以直接计算出 f₁(x)d₁(x)
  3. 迭代计算:对于更多的工程,我们使用已知的 f₋₁(x)d₋₁(x) 来计算 fᵢ(x)dᵢ(x)

1. 只分配给第1个工程

资源分配表:

x01234
f₁(x)713161719
d₁(x)01234

解释:

  • 我们首先考虑只有一个工程的情况,直接计算每个资源份额下的利润。
  • d₁(x) 表示在给定资源份额下,第1个工程的资源分配。

2. 分配给前2个工程

资源分配表:

x01234
f₂(x)1319252830
d₂(x)00/1112

计算过程:

  1. 当 x = 0 时:

    • 只有第1个工程可以使用资源,利润为 f₂(0) = f₁(0) + G₂(0) = 7 + 6 = 13
    • 资源全部分配给第1个工程,d₂(0) = 0
  2. 当 x = 1 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₂(0) + f₁(1) = 6 + 13 = 19
      • G₂(1) + f₁(0) = 12 + 7 = 19
    • 利润相同,可以选择任意一种分配方式,d₂(1) 可以是 0 或 1。
  3. 当 x = 2 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₂(0) + f₁(2) = 6 + 16 = 22
      • G₂(1) + f₁(1) = 12 + 13 = 25
      • G₂(2) + f₁(0) = 14 + 7 = 21
    • 选择利润最大的分配方式,d₂(2) = 1
  4. 当 x = 3 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₂(0) + f₁(3) = 6 + 17 = 23
      • G₂(1) + f₁(2) = 12 + 16 = 28
      • G₂(2) + f₁(1) = 14 + 13 = 27
      • G₂(3) + f₁(0) = 16 + 7 = 23
    • 选择利润最大的分配方式,d₂(3) = 1
  5. 当 x = 4 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₂(0) + f₁(4) = 6 + 19 = 25
      • G₂(1) + f₁(3) = 12 + 17 = 29
      • G₂(2) + f₁(2) = 14 + 16 = 30
      • G₂(3) + f₁(1) = 16 + 13 = 29
      • G₂(4) + f₁(0) = 18 + 7 = 25
    • 选择利润最大的分配方式,d₂(4) = 2

解释为什么这么做:

  • 我们通过比较不同分配方式下的利润,选择能够带来最大利润的分配方案。
  • 这种方法确保了在有限的资源下,我们能够获得最大的经济回报。
  • 动态规划的优势在于它避免了重复计算相同的子问题,提高了计算效率。

通过以上步骤,我们可以得到在不同资源分配下的最大利润以及各个工程的资源分配份额。

3. 分配给前3个工程

步骤

  1. 定义子问题:我们定义 f₃(x) 为将 x 份资源分配给前3个工程时的最大利润,d₃(x) 为在 f₃(x) 最大时,分配给第3个工程的资源份额。

计算过程

  1. 当 x = 0 时:

    • 只有第1和第2个工程可以使用资源,利润为 f₃(0) = f₁(0) + G₂(0) + G₃(0) = 7 + 6 + 5 = 18
    • 资源全部分配给第1和第2个工程,d₃(0) = 0
  2. 当 x = 1 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₃(0) + f₂(1) = 5 + 19 = 24
      • G₃(1) + f₂(0) = 18 + 13 = 31
    • 选择利润最大的分配方式,d₃(1) = 1
  3. 当 x = 2 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₃(0) + f₂(2) = 5 + 25 = 30
      • G₃(1) + f₂(1) = 18 + 19 = 37
      • G₃(2) + f₂(0) = 19 + 13 = 32
    • 选择利润最大的分配方式,d₃(2) = 1
  4. 当 x = 3 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₃(0) + f₂(3) = 5 + 28 = 33
      • G₃(1) + f₂(2) = 18 + 25 = 43
      • G₃(2) + f₂(1) = 19 + 19 = 38
      • G₃(3) + f₂(0) = 20 + 13 = 33
    • 选择利润最大的分配方式,d₃(3) = 1
  5. 当 x = 4 时:

    • 比较不同分配方式的利润,选择最大的利润:
      • G₃(0) + f₂(4) = 5 + 30 = 35
      • G₃(1) + f₂(3) = 18 + 28 = 46
      • G₃(2) + f₂(2) = 19 + 25 = 44
      • G₃(3) + f₂(1) = 20 + 19 = 39
      • G₃(4) + f₂(0) = 22 + 13 = 35
    • 选择利润最大的分配方式,d₃(4) = 1

资源分配表:

xf₃(x)d₃(x)
0180
1311
2371
3431
4461

解释为什么这么做

  • 我们通过比较不同分配方式下的利润,选择能够带来最大利润的分配方案。
  • 这种方法确保了在有限的资源下,我们能够获得最大的经济回报。
  • 动态规划的优势在于它避免了重复计算相同的子问题,提高了计算效率。

步骤二:求各个阶段的最大利润 gᵢ 和分配份额 qᵢ

  • 最大利润

    • g₁ = 19
    • g₂ = 30
    • g₃ = 46
  • 资源分配份额

    • q₁ = 4
    • q₂ = 4
    • q₃ = 4

步骤三:计算全局的最大利润 optg、最大的工程数目 k、总的最优分配份额 optx(k)

  • 全局最大利润optg = 46
  • 最大的工程数目k = 3
  • 总的最优分配份额optx₃ = 4

步骤四: 计算各个工程的最优分配份额 optq(x)

  1. 第3个工程

    • optq₃ = d₃(optx₃) = d₃(4) = 1
    • optx₂ = optx₃ - optq₃ = 4 - 1 = 3
  2. 第2个工程

    • optq₂ = d₂(optx₂) = d₂(3) = 1
    • optx₁ = optx₂ - optq₂ = 3 - 1 = 2
  3. 第1个工程

    • optq₁ = d₁(optx₁) = d₁(2) = 2

最终决策结果

  • 分别分配给第1、2、3工程 2、1、1 份资源,可得最大利润 46。

代码

#define _CRT_NO_SECURE_WARNINGS // 忽略某些安全警告

#include<stdio.h> // 包含标准输入输出库
#include<iostream> // 包含输入输出流库

using namespace std; // 使用标准命名空间

int main() { // 主函数开始
    int m = 0; // 项目数
    int n = 0; // 投资金额
    int num = 0; // 用于记录第三个项目的投资金额
    float q[100][100] = { 0 }; // 一个二维数组,用来存储每个项目不同投资金额下的利润
    float f[100] = { 0 }; // 一个一维数组,用于存储当前最大收益
    float a[100][100] = { 0 }; // 一个二维数组,记录当前投资利益最大时每个项目所分配的投资数
    float temp[100] = { 0 }; // 一个一维数组,临时记录正在计算的最大收益
    float gain[100] = { 0 }; // 一个一维数组,用来存储每个项目的利润(未使用)
    int rest = 0; // 剩余投资金额(未使用)

    cout << "请输入项目数:"; // 输出提示信息
    cin >> m; // 从键盘读取项目数
    cout << "请输入投资金额:"; // 输出提示信息
    cin >> n; // 从键盘读取投资金额
    cout << "请输入原始利润数据:" << endl; // 输出提示信息

    // 循环读取每个项目的利润数据
    for (int i = 1; i <= m; i++) {
        cout << "投资#" << i << " "; // 输出提示信息
        for (int j = 0; j <= n; j++) {
            cin >> q[i][j]; // 从键盘读取利润数据
        }
    }

    // 初始化第一个项目的最大利益
    for (int j = 0; j <= n; j++) { // 从0到n投资
        f[j] = q[1][j]; // 第一个项目的最大利益
        a[1][j] = j; // 分配给第一个项目的投资金额
    }

    // 计算后面项目的最大收益
    for (int k = 2; k < m; k++) { // 从第二个项目开始
        for (int j = 0; j <= n; j++) { // 遍历所有可能的投资金额
            temp[j] = q[k][j]; // 初始化临时数组
            a[k][j] = 0; // 初始化分配数组
        }
        for (int j = 0; j <= n; j++) { // 遍历所有可能的投资金额
            for (int i = 0; i <= j; i++) { // 遍历所有可能的分配方案
                if (f[j - i] + q[k][i] > temp[j]) { // 如果当前方案更好,则更新
                    temp[j] = f[j - i] + q[k][i]; // 更新最大收益
                    a[k][j] = i; // 更新分配给当前项目的投资金额
                }
            }
        }
        for (int j = 0; j <= n; j++) { // 更新当前最大收益数组
            f[j] = temp[j];
        }
    }

    // 计算最后一个项目的最大收益
    for (int i = 0; i <= n; i++) {
        temp[i] = q[m][i] + f[n - i]; // 计算最大收益
    }
    for (int j = 0; j < n; j++) { // 找到最大收益对应的投资金额
        if (temp[j] < temp[j + 1]) {
            num = j + 1; // 记录第三个项目的投资金额
        }
    }

    // 输出第三个项目的所有可能收益
    cout << "第三个项目投资收益:" << endl;
    for (int i = 0; i <= n; i++) {
        cout << temp[i] << "  "; // 输出每个可能的最大收益
    }
    cout << "\n";

    // 输出最优投资方案
    cout << "当进行如下投资是收益最大:" << endl;
    cout << "第一个项目投资:" << n - num - a[2][n - num] << endl; // 输出第一个项目的投资金额
    cout << "第二个项目投资:" << a[2][n - num] << endl; // 输出第二个项目的投资金额
    cout << "第三个项目投资:" << num << endl; // 输出第三个项目的投资金额
    cout << "最大投资效益为:" << temp[num] << endl; // 输出最大收益

    system("pause"); // 暂停程序,等待用户操作
    return 0; // 主函数结束
}

标签:最大,工程,资源分配,int,规划法,动态,分配,利润
From: https://blog.csdn.net/qq_52291558/article/details/141829740

相关文章

  • 【Canvas与艺术】十边螺线动态顺时针扩大光阑
    【成图】【代码】<!DOCTYPEhtml><htmllang="utf-8"><metahttp-equiv="Content-Type"content="text/html;charset=utf-8"/><head><title>十边螺线动态扩大光阑</title><styletype="text/css&quo......
  • 【Canvas与艺术】十边螺线动态缩小光阑
    【成图】【代码】<!DOCTYPEhtml><htmllang="utf-8"><metahttp-equiv="Content-Type"content="text/html;charset=utf-8"/><head><title>十边螺线动态缩小光阑</title><styletype="text/css&quo......
  • 我的动态规划题单
    可恶的动态规划,每次考试基本都写不出来,于是特意整理个动态规划提单因为博客园好像标题和网址不能同时用,所以本来点标题就可以跳转了,现在要自己去搜,大多是洛谷的题,搜不到就是内部题。1.CF1620FBipartiteArray题意等价于:要把这些点分成两部分,每一部分之间都没有边相连,等价于......
  • 复旦大学王龑团队发布《静态与动态情感的面部表情识别》综述
    论文链接:https://arxiv.org/pdf/2408.15777复旦大学,王龑博士后领衔,发布《静态与动态情感的面部表情识别》(ASurveyonFacialExpressionRecognitionofStaticandDynamicEmotions)综述,对基于图像的静态面部表情识别(SFER)和基于视频的动态面部表情识别(DFER)方法进行了全面综述,......
  • 每日一题08:说一下Spring AOP动态代理模式
    回答1:SpringAOP使用的动态代理,所谓的动态代理就是说AOP框架不会去修改字节码,而是每次运行时在内存中临时为方法生成一个AOP对象,这个AOP对象包含了目标对象的全部方法,并且在特定的切点做了增强处理,并回调原对象的方法。SpringAOP中的动态代理主要有两种方式,JDK动态代理和CGL......
  • vue3+vite注册动态路由的实践
    //route/index.jsimport{createRouter,createWebHistory}from'vue-router'importHomeViewfrom'../views/HomeView.vue'//constcomp=()=>import('../views/AboutView.vue')//console.log('comp:>>......
  • 动态代理大揭秘,带你彻底弄清楚动态代理!
    https://segmentfault.com/a/1190000040680716前言代理模式是一种设计模式,能够使得在不修改源目标的前提下,额外扩展源目标的功能。即通过访问源目标的代理类,再由代理类去访问源目标。这样一来,要扩展功能,就无需修改源目标的代码了。只需要在代理类上增加就可以了。其实代理模式......
  • JS的DOM高级编程和动态添加表格行的小案例实现
    DOM高级编程(DocumentobjectModal)DOM概述DOM-DocumentObjectModal,它是W3C国际组织的一套Web标准DOM是一种与浏览器、平台、语言无关的接口Dom认为:html文档中每个成员都是一个节点,根据节点的不同,可分为:文档节点(document)元素节点(element)属性节点(attribute)文本节点(tex......
  • 动态调整pod资源
    #运行时动态调整pod资源##1.控制平面组件特性门控编辑如下路径/etc/kubernetes/manifests/的kube-apiserver.yaml,kube-controller-manager.yaml,kube-scheduler.yaml配置文件,在各自容器启动命令行参数添加配置项:---featuregates=InPlacePodVerticalScaling......
  • 49. 静态联编动态联编及多态原理
    静态联编动态联编静态多态(就是函数重载)和动态多态静态多态:函数重载,运算符重载动态多态://先有继承关系//父类中有虚函数,子类重写父类中的虚函数//父类的指针或引用指向子类的对象静态多态在编译阶段绑定地址,地址早绑定,静态联编动态多次在运行阶段绑定地址,地址晚绑定,动态联......