工作收益最大化问题——动态规划Java实现

这里写自定义目录标题

动态规划

在Fibonacci函数里面,最常规最简单的做法是用递归的方式。
F(n)=F(n-1)+F(n-2)就是费波那契数列的定义。
例如:
1 1 2 3 5 8 13,就是一个费波那契数列

public   static int Fibonacci(int n){
	if(n<=0){
		return 0;
	}
	if(n==1||n==2){
		return 1;
	}
	else{
		return Fibonacci2(n-1)+Fibonacci2(n-2);
	}
}

它的代码如上。
用递归很容易实现,但是也会出现一个问题,若n变的越来越大,效率会成指数增长,时间复杂度为O(2n)。
如果n过大,甚至可能会溢出内存(反正我n太大eclipse就没反应了)。

这是为什么呢?

这是f(n),n从1到8所调用的函数
《工作收益最大化问题——动态规划Java实现》
不难看出,如果要计算F(8),前面会计算很多次重复的数据。
如果我们先从F(1)开始算起,把计算的结果存储起来是否可以避免重复计算呢?
F(1)=1
F(2)=1
F(3)=F(1)+F(2)=2
F(4)=F(3)+F(2)=3
.
.
.

F(n)=F(n-1)+F(n-2)
创建一个数组,把前面的结果先存储起来,等后面的数据需要时直接调用,成为一个有效的解决办法。

工作效益问题

题:当前有N个工作,,每个工作有相应的收益,但是每个工作的时间不同,且每次只能在同一时间段做一份工作,例如:选择工作1,则在1~4时间段内不能做其他工作。问怎么选择工作时工作收益最大化?
《工作收益最大化问题——动态规划Java实现》
(图来源于B站作者:正月点灯笼)

不难看出
如果要选择工作8,则收益为4,但是只能选择编号为6以前的工作,
如果不选择工作8,则无收益,但是可以选择编号为7以前的工作。

这就是动态分配的核心思想:选和不选
《工作收益最大化问题——动态规划Java实现》
(+代表选择,-代表不选择,)
若继续细化下去,opt(6)就会分为选择:opt(2)+V6和不选择opt(5),
其中opt(5)就和我们选择opt(8)时计算的opt(5)重复计算,所以要存储起来。
用一个数组即可!

每一个结点在选择的时候,比较2种方案取最大值,就是这个结点的最优方案。

我们先算每个任务如果选择,它前面最近可选择的任务
不难从图中看出:

ipre(i)
10
20
30
41
50
62
73
85

(i:工作编号,pre(i):若选择编号为i的工作,则工作i之前能选择的最近工作)
例如:
选择工作7,时间为6~11,同一时间只能做一个工作,所以最近只能选择时间6之前的工作,即最近结束的是工作3。

根据这个思路,代码如下

public class Main {
	public static void main(String[] args) {
		int n = 8;	//机器人个数
		int[] pre = {0,0,0,0,1,0,2,3,5};	//选择这个工作之后前驱最近工作下标
		int[] profit = {5,1,8,4,6,3,2,4};	//工作收益
		int opt[] = new int[n+1];
		
		opt[0]=0;
		
		for(int i=1;i<opt.length;i++){
			opt[i]=Math.max(opt[i-1], opt[pre[i]]+profit[i-1]);	//比较2种方案,选择和不选择,取收益最大的方案
		}
		
		for(int i=1;i<n+1;i++){
			System.out.println(opt[i]);
		}
	}
}

运行输出
《工作收益最大化问题——动态规划Java实现》
即为每个结点的最佳方案。
对于这个题目,则就是根节点的最佳方案,在数组中就是最后一个计算出来的,在数组的最后,即为13

感谢

笔者也为初学者,感谢Bilibili作者正月点灯笼,从他的教学中学习而来。
如有不足和错误,欢迎指正!

    原文作者:寒斫
    原文地址: https://blog.csdn.net/qq_36379203/article/details/88363663
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞