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

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

问题描述

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

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

目标

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

步骤

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

1. 只分配给第1个工程

资源分配表：

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

解释：

我们首先考虑只有一个工程的情况，直接计算每个资源份额下的利润。
d₁(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

计算过程：

当 x = 0 时：
- 只有第1个工程可以使用资源，利润为 f₂(0) = f₁(0) + G₂(0) = 7 + 6 = 13。
- 资源全部分配给第1个工程，d₂(0) = 0。
当 x = 1 时：
- 比较不同分配方式的利润，选择最大的利润：
  - G₂(0) + f₁(1) = 6 + 13 = 19
  - G₂(1) + f₁(0) = 12 + 7 = 19
- 利润相同，可以选择任意一种分配方式，d₂(1) 可以是 0 或 1。
当 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。
当 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。
当 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个工程

步骤

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

计算过程

当 x = 0 时：
- 只有第1和第2个工程可以使用资源，利润为 f₃(0) = f₁(0) + G₂(0) + G₃(0) = 7 + 6 + 5 = 18。
- 资源全部分配给第1和第2个工程，d₃(0) = 0。
当 x = 1 时：
- 比较不同分配方式的利润，选择最大的利润：
  - G₃(0) + f₂(1) = 5 + 19 = 24
  - G₃(1) + f₂(0) = 18 + 13 = 31
- 选择利润最大的分配方式，d₃(1) = 1。
当 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。
当 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。
当 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。

资源分配表：

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

解释为什么这么做

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

步骤二：求各个阶段的最大利润 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)

第3个工程：
- optq₃ = d₃(optx₃) = d₃(4) = 1
- optx₂ = optx₃ - optq₃ = 4 - 1 = 3
第2个工程：
- optq₂ = d₂(optx₂) = d₂(3) = 1
- optx₁ = optx₂ - optq₂ = 3 - 1 = 2
第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; // 主函数结束
}