草庐IT

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

粒粒米z 2024-02-02 原文

问题分析：

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

（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）

问题资源分配ltmargin-lefttext-align算法动态规划云计算

有关资源分配问题【算法设计与分析】＜动态规划问题＞的更多相关文章

  1. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  2. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  3. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  4. Ruby Koans about_array_assignment - 非平行与平行分配歧视 - 2

    通过ruby​​koans.com，我在about_array_assignment.rb中遇到了这两段代码你怎么知道第一个是非并行赋值，第二个是一个变量的并行赋值？在我看来，除了命名差异之外，代码几乎完全相同。4deftest_non_parallel_assignment5names=["John","Smith"]6assert_equal["John","Smith"],names7end45deftest_parallel_assignment_with_one_variable46first_name,=["John","Smith"]47assert_equal'John

  5. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  6. ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2

    我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它​​不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。 最佳答案 如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数

  7. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  8. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  9. ruby - 在 Ruby 中重新分配常量时抛出异常？ - 2

    我早就知道Ruby中的“常量”(即大写的变量名)不是真正常量。与其他编程语言一样，对对象的引用是唯一存储在变量/常量中的东西。(侧边栏:Ruby确实具有“卡住”引用对象不被修改的功能，据我所知，许多其他语言都没有提供这种功能。)所以这是我的问题:当您将一个值重新分配给常量时，您会收到如下警告:>>FOO='bar'=>"bar">>FOO='baz'(irb):2:warning:alreadyinitializedconstantFOO=>"baz"有没有办法强制Ruby抛出异常而不是打印警告？很难弄清楚为什么有时会发生重新分配。 最佳答案

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐