問題分析：
(要把問題分為多步解決，每步求出子問題的多個最優(yōu)策略后一步依賴于上一步的最有策略，最后一步得出問題的解)
（1）首先要考慮分配給項目A的資金與利潤的關(guān)系。得到此時投資數(shù)x與其相對應(yīng)的
的關(guān)系。
（2）其次要考慮分配給前兩個項目A，B的總資金
與利潤的關(guān)系。得到此時投資數(shù)x與其相對應(yīng)的
的關(guān)系。
（3）最后考慮分配給第三個項目C的資金
與利潤的關(guān)系得到此時投資數(shù)x與其相應(yīng)的
的關(guān)系。
最終利潤為
此時x為投資C項目的資金。
數(shù)學(xué)建模：
開辟二維數(shù)組q來存儲原始利潤的數(shù)據(jù)
另開辟一維數(shù)組f儲存當(dāng)前最大收益情況
開辟記錄中間結(jié)果的一維數(shù)組temp,記錄正在計算的最大收益
開辟二維數(shù)組a記錄當(dāng)前投資最大收益時每個項目所分配的投資數(shù)
數(shù)組gain存儲第i個工程投資數(shù)的最后結(jié)果
階段劃分，逐步去求解每一個項目在不同投資額下的最大收益
實驗代碼：
#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 }; //用于存儲當(dāng)前最大收益
float a[100][100] = { 0 }; //記錄當(dāng)前投資利益最大是每個項目所分配的投資數(shù)
float temp[100] = { 0 }; //記錄正在計算的最大收益
float gain[100] = { 0 };
int rest = 0;
cout << "請輸入項目數(shù):";
cin >> m;
cout << "請輸入投資金額:";
cin >> n;
cout << "請輸入原始利潤數(shù)據(jù):" << 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 << "當(dāng)進(jìn)行如下投資是收益最大:" << 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;
}時間復(fù)雜度分析：文章來源：http://www.zghlxwxcb.cn/news/detail-401263.html
O（m*n）文章來源地址http://www.zghlxwxcb.cn/news/detail-401263.html
到了這里，關(guān)于資源分配問題【算法設(shè)計與分析】＜動態(tài)規(guī)劃問題＞的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[spark]spark資源分配](https://imgs.yssmx.com/Uploads/2024/02/474280-1.png)
