资源分配问题【算法设计与分析】＜动态规划问题＞-Toy模板网

这篇具有很好参考价值的文章主要介绍了资源分配问题【算法设计与分析】＜动态规划问题＞。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题分析：

(要把问题分为多步解决，每步求出子问题的多个最优策略后一步依赖于上一步的最有策略，最后一步得出问题的解)

（1）首先要考虑分配给项目A的资金与利润的关系。得到此时投资数x与其相对应的资源分配问题【算法设计与分析】＜动态规划问题＞的关系。

（2）其次要考虑分配给前两个项目A，B的总资金资源分配问题【算法设计与分析】＜动态规划问题＞与利润的关系。得到此时投资数x与其相对应的的关系。

（3）最后考虑分配给第三个项目C的资金资源分配问题【算法设计与分析】＜动态规划问题＞与利润的关系得到此时投资数x与其相应的的关系。

最终利润为资源分配问题【算法设计与分析】＜动态规划问题＞此时x为投资C项目的资金。

数学建模：

开辟二维数组q来存储原始利润的数据

另开辟一维数组f储存当前最大收益情况

开辟记录中间结果的一维数组temp,记录正在计算的最大收益

开辟二维数组a记录当前投资最大收益时每个项目所分配的投资数

数组gain存储第i个工程投资数的最后结果

阶段划分，逐步去求解每一个项目在不同投资额下的最大收益

实验代码：

#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;
}

时间复杂度分析：

O（m*n）文章来源地址https://www.toymoban.com/news/detail-401263.html

到了这里，关于资源分配问题【算法设计与分析】＜动态规划问题＞的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！