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

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

引用

CSDN

1.

https://blog.csdn.net/qq_52291558/article/details/141829740

动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。本文将通过一个具体的资源分配问题，详细讲解动态规划法的求解过程。

问题描述

把4个份额的资源分配给3个工程，给定利润表如下表所示，写出资源的最优分配方案的求解过程。

4份资源分配给3个工程的利润表

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

目标

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

步骤

1. 定义子问题：我们定义
   $f_i(x)$
   为将 x 份资源分配给前 i 个工程时的最大利润，
   $d_i(x)$
   为在
   $f_i(x)$
   最大时，分配给第 i 个工程的资源份额。

2. 初始化：对于只有一个工程的情况，我们可以直接计算出
   $f_1(x)$
   和
   $d_1(x)$
   。

3. 迭代计算：对于更多的工程，我们使用已知的
   $f_{i-1}(x)$
   和
   $d_{i-1}(x)$
   来计算
   $f_i(x)$
   和
   $d_i(x)$
   。

1. 只分配给第1个工程

资源分配表：

x  0  1  2  3  4
f₁(x)  7  13  16  17  19
d₁(x)  0  1  2  3  4

解释：

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

2. 分配给前2个工程

资源分配表：

x  0  1  2  3  4
f₂(x)  13  19  25  28  30
d₂(x)  0  0/1  1  1  2

计算过程：

1. 当 x = 0 时：

• 只有第1个工程可以使用资源，利润为
  $f_2(0) = f_1(0) + G_2(0) = 7 + 6 = 13$
  。
• 资源全部分配给第1个工程，
  $d_2(0) = 0$
  。

2. 当 x = 1 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_2(0) + f_1(1) = 6 + 13 = 19$
• $G_2(1) + f_1(0) = 12 + 7 = 19$
• 利润相同，可以选择任意一种分配方式，
  $d_2(1)$
  可以是 0 或 1。

3. 当 x = 2 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_2(0) + f_1(2) = 6 + 16 = 22$
• $G_2(1) + f_1(1) = 12 + 13 = 25$
• $G_2(2) + f_1(0) = 14 + 7 = 21$
• 选择利润最大的分配方式，
  $d_2(2) = 1$
  。

4. 当 x = 3 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_2(0) + f_1(3) = 6 + 17 = 23$
• $G_2(1) + f_1(2) = 12 + 16 = 28$
• $G_2(2) + f_1(1) = 14 + 13 = 27$
• $G_2(3) + f_1(0) = 16 + 7 = 23$
• 选择利润最大的分配方式，
  $d_2(3) = 1$
  。

5. 当 x = 4 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_2(0) + f_1(4) = 6 + 19 = 25$
• $G_2(1) + f_1(3) = 12 + 17 = 29$
• $G_2(2) + f_1(2) = 14 + 16 = 30$
• $G_2(3) + f_1(1) = 16 + 13 = 29$
• $G_2(4) + f_1(0) = 18 + 7 = 25$
• 选择利润最大的分配方式，
  $d_2(4) = 2$
  。

解释为什么这么做：

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

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

3. 分配给前3个工程

步骤

1. 定义子问题：我们定义
   $f_3(x)$
   为将 x 份资源分配给前3个工程时的最大利润，
   $d_3(x)$
   为在
   $f_3(x)$
   最大时，分配给第3个工程的资源份额。

计算过程

1. 当 x = 0 时：

• 只有第1和第2个工程可以使用资源，利润为
  $f_3(0) = f_1(0) + G_2(0) + G_3(0) = 7 + 6 + 5 = 18$
  。
• 资源全部分配给第1和第2个工程，
  $d_3(0) = 0$
  。

2. 当 x = 1 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_3(0) + f_2(1) = 5 + 19 = 24$
• $G_3(1) + f_2(0) = 18 + 13 = 31$
• 选择利润最大的分配方式，
  $d_3(1) = 1$
  。

3. 当 x = 2 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_3(0) + f_2(2) = 5 + 25 = 30$
• $G_3(1) + f_2(1) = 18 + 19 = 37$
• $G_3(2) + f_2(0) = 19 + 13 = 32$
• 选择利润最大的分配方式，
  $d_3(2) = 1$
  。

4. 当 x = 3 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_3(0) + f_2(3) = 5 + 28 = 33$
• $G_3(1) + f_2(2) = 18 + 25 = 43$
• $G_3(2) + f_2(1) = 19 + 19 = 38$
• $G_3(3) + f_2(0) = 20 + 13 = 33$
• 选择利润最大的分配方式，
  $d_3(3) = 1$
  。

5. 当 x = 4 时：

• 比较不同分配方式的利润，选择最大的利润：
• $G_3(0) + f_2(4) = 5 + 30 = 35$
• $G_3(1) + f_2(3) = 18 + 28 = 46$
• $G_3(2) + f_2(2) = 19 + 25 = 44$
• $G_3(3) + f_2(1) = 20 + 19 = 39$
• $G_3(4) + f_2(0) = 22 + 13 = 35$
• 选择利润最大的分配方式，
  $d_3(4) = 1$
  。

资源分配表：

x  f₃(x)  d₃(x)
0  18  0
1  31  1
2  37  1
3  43  1
4  46  1

解释为什么这么做

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

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

• 最大利润：

• $g_1 = 19$

• $g_2 = 30$

• $g_3 = 46$

• 资源分配份额：

• $q_1 = 4$

• $q_2 = 4$

• $q_3 = 4$

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

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

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

1. 第3个工程：

• $optq_3 = d_3(optx_3) = d_3(4) = 1$
• $optx_2 = optx_3 - optq_3 = 4 - 1 = 3$

2. 第2个工程：

• $optq_2 = d_2(optx_2) = d_2(3) = 1$
• $optx_1 = optx_2 - optq_2 = 3 - 1 = 2$

3. 第1个工程：

• $optq_1 = d_1(optx_1) = d_1(2) = 2$

最终决策结果

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

代码

/* 资源分配问题 */
#include <stdio.h>
#define N 7  // 定义常量 N，代表项目的数量
#define M 3  // 定义常量 M，代表资源的种类数量
float profit[M+1][N+1];  // 存储不同资源分配方案下的利润，M+1 和 N+1 是因为数组是从 1 开始计数的
// 测试数据，代表不同资源分配下的利润
float test[24] = {0, 0.11, 0.13, 0.15, 0.21, 0.24, 0.3, 0.35,
                  0, 0.12, 0.16, 0.21, 0.23, 0.25, 0.24, 0.34,
                  0, 0.08, 0.12, 0.2,  0.24, 0.25, 0.3, 0.35};
int main() {
    float temp[N+1];  // 用来存储当前正在计算的最大利润
    float f[N+1];  // 用来存储当前的最大利润
    int a[M+1][N+1];  // 资源分配表，包括分配为0的情况
    int gain[M];  // 用来存储每个项目最终分配的资源数量
    int number = 0;  // 用来记录测试数据的索引
    // 给初始的利润表 profit 赋值
    for (int i = 0; i <= M; i++) {
        for (int j = 0; j <= N; j++) {
            profit[i][j] = test[number++];  // 从测试数据中获取利润值
            if (i < 1) {
                // 如果是第一个项目，初始化资源分配表
                a[1][j] = j;  // 分配所有资源给第一个项目
                f[j] = profit[0][j];  // 初始化当前的最大利润
                temp[j] = profit[0][j];  // 存储只有一个项目时的最大利润
            }
        }
    }
    int layer = 0;  // 用来记录当前处理的项目层级
    for (int k = 2; k <= M; k++) {  // 依次加入新项目
        layer++;
        for (int i = 0; i <= N; i++) {  // 不同资源数量的分配方案
            for (int j = 0; j <= i; j++) {  // 分配给新项目的资源数
                if (profit[layer][j] + temp[i - j] > f[i]) {  // 如果新分配方案的利润更高
                    f[i] = profit[layer][j] + temp[i - j];  // 更新当前的最大利润
                    a[k][i] = j;  // 记录新项目的资源分配
                    printf("sum3=%3.2f\n", f[i]);  // 打印当前的最大利润
                }
            }
        }
        for (int j = 0; j <= N; j++) {  // 更新已计算的项目资源分配利益总表
            temp[j] = f[j];
        }
        printf("第一次结束：\n");
    }
    int rest = N;  // 剩余的资源数量
    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("sum=%3.2f:\n", f[N]);  // 打印总的最大利润
}