`
songzi0206
  • 浏览: 158856 次
  • 性别: Icon_minigender_1
  • 来自: 上海
博客专栏
Group-logo
All are from ...
浏览量:33816
Group-logo
Programming w...
浏览量:19683
社区版块
存档分类
最新评论

动态规划之活动选择--代码实现

 
阅读更多



   昨天对活动选择的动态规划解做了分析和描述,今天就来简单的实现一下代码,并用实例来验证其运行的正确性。

   //基础类用来保存动态的集合A[i][j]

class DynamicSet{
		public static DynamicSet empty = new DynamicSet(null);
		
		List<Integer> resultSet = null;
		
		public DynamicSet(){
			resultSet = new ArrayList<Integer>();
		}
		
		public DynamicSet(List<Integer> rs){
			this.resultSet = rs;
		}

		@Override
		public String toString() {
			return resultSet == null ? "empty" : resultSet.toString();
		}
	}

 //算法实现方法

public static void selectActivity(int[] s, int[] f, int n){
		s[0] = f[0] = 0;
		s[n+1] = f[n+1] = Integer.MAX_VALUE;
		//Initialize the int[][]c and DynmicSet[][]A
		int[][] c = new int[n+2][n+2];
		DynamicSet[][] A = new DynamicSet[n+2][n+2];
		for( int i = 0; i <= n + 1; i++){
			for(int j = 0; j <= i; j++){
				c[i][j] = 0;
				A[i][j] = DynamicSet.empty;
			}
		}
		//Start to calculation the values for the A and C
		for( int t = 1; t <= n+1; ++t){
			for( int i = 0; i <= n - t + 1; ++i){
 				int j = i + t;
				if( f[i] >= s[j]){
					c[i][j] = 0;
					A[i][j] = DynamicSet.empty;
				}else{
					for(int k = i+1; k <= j - 1; k++){
						if( f[i] <= s[k] && f[k] <= s[j]){
							if( c[i][j] < c[i][k] + 1 + c[k][j]){
								c[i][j] = c[i][k] + 1 + c[k][j];
								resetDynmaicSetA_i_j(A,i,j,k);
							}
						}
					}
					//set DynamicSet.empty for the null set, this step could be omit
					if(A[i][j] == null)
						A[i][j] = DynamicSet.empty;
				}
			}
		}
		System.out.println(c[0][n+1]);
		System.out.println(A[0][n+1].resultSet.toString());
	}

 //辅助方法,用来合并集合 A[i][j] = A[i][k] ∪ k ∪ A[k][j]

  

private static void resetDynmaicSetA_i_j(DynamicSet[][] A, int i, int j,int k) {
		if( A[i][j] == null )
			A[i][j] = new DynamicSet();
		if( A[i][j].resultSet == null )
			A[i][j].resultSet = new ArrayList<Integer>();
		A[i][j].resultSet.clear();
		
		if( A[i][k] != null && A[i][k] != DynamicSet.empty )
			A[i][j].resultSet.addAll(A[i][k].resultSet);
		A[i][j].resultSet.add(k);
		if( A[k][j] != null && A[k][j] != DynamicSet.empty )
			A[i][j].resultSet.addAll(A[k][j].resultSet);
	}

   

   测试代码,假设现在有11个活动已经按结束时间fi排好序:

      

i 1 2 3 4 5 6 7 8 9 10 11
s[i] 1 3 0 5 3 5 6 8 8 2 12
f[i] 4 5 6 7 8 9 10 11 12 13 14

 

 

 

 

 

 

 

 

 

 

则测试代码如下:

public static void main(String[] args){
		int n = 11;
		int[] s = new int[]{0,1,3,0,5,3,5, 6, 8, 8, 2,12,0};
		int[] f = new int[]{0,4,5,6,7,8,9,10,11,12,13,14,0};
		
		selectActivity(s,f,n);
	}

 

 

运行结果:

4 // c[0][12]
[1, 4, 8, 11] //A[0][12]

内存中保存的值:

c[][]:

 

[0, 0, 0, 0, 1, 0, 1, 1, 2, 2, 0, 3, 4],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2, 3],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2, 3],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

A[][]:

 

[empty, empty, empty, empty, [1], empty, [1], [1], [1, 4], [1, 4], empty, [1, 4, 8], [1, 4, 8, 11]]
[empty, empty, empty, empty, empty, empty, empty, empty, [4], [4], empty, [4, 8], [4, 8, 11]]
[empty, empty, empty, empty, empty, empty, empty, empty, [4], [4], empty, [4, 8], [4, 8, 11]] 
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [7], [7, 11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [8], [8, 11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [8], [8, 11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, [11]]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty]
[empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty, empty]

分享到:
评论

相关推荐

    会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf

    动态规划是另一种解决会议安排问题的方法,思路是将活动按结束时间递增排序,然后使用动态规划表dp[i]记录活动i为结尾的最大的活动安排数。如果活动i可以被安排上,则dp[i]=dp[i-1]+1,否则dp[i]=dp[i-1]。最后,...

    acm基础之--acm常用代码1

    标题中的"acm基础之--acm常用代码1"表明这是一份针对ACM编程初学者的资源,可能包含了一些基本的算法和代码实现。 描述中提到这是一个“网页文件”,这意味着它可能是一个集合了各种代码示例的在线文档,便于阅读和...

    活动选择问题-算法设计与分析

    在"Activity_Selection"这个压缩包中,可能包含了关于活动选择问题的更多实例、代码实现、复杂度分析或其他相关材料。通过深入学习和实践这些内容,我们可以更好地理解和掌握活动选择问题的算法设计与分析方法,以及...

    代码随想录 动态规划、回溯、递归、二叉树、贪心

    《代码随想录》是一本深受程序员喜爱的编程学习资料,尤其在算法领域,它提供了丰富的实例和深入的解析,帮助读者理解并掌握动态规划、回溯、递归、二叉树以及贪心等核心算法。这些算法是解决复杂计算问题的基础工具...

    MDL-Matlab代码.rar

    综上所述,MDL-Matlab代码.rar提供的MATLAB代码实现了最小完成时间算法,用于解决任务调度问题。通过理解和分析这些代码,我们可以学习如何在实际应用中使用动态规划、贪心策略或启发式方法来优化任务的完成时间。...

    程序员代码面试指南:IT名企算法与数据结构题目解---源代码

    4. **动态规划**:动态规划是一种解决最优化问题的策略,通过将大问题分解为子问题来求解。书中可能包含背包问题、最长公共子序列、斐波那契数列等经典例子。 5. **贪心算法**:贪心算法在每一步选择局部最优解,...

    C++实现oj算法代码-贪心算法.zip

    - 探索动态规划和贪心算法的区别,理解何时贪心策略适用,何时需要更全面的动态规划方法。 - 学习并练习使用C++ STL的高级特性,如迭代器、函数对象和模板元编程,以提高代码效率和可读性。 总之,这个压缩包提供...

    swift-收集算法题的解题代码实现

    "swift-收集算法题的解题代码实现"这个项目显然包含了使用Swift解决各种算法问题的实际代码示例。以下是对这些算法题目的详细解读和相关知识点的深入探讨。 1. **排序算法**: - **快速排序**:Swift中可以使用`...

    贪心算法与动态规划

    **1.5 代码实现** ```c++ int greedySelector(int *s, int *f, bool *a) { a[1] = true; int j = 1; int count = 1; for (int i = 2; i ; i++) { if (s[i] &gt;= f[j]) { a[i] = true; j = i; count++; } else...

    算法导论C++实现代码

    6. **动态规划**:动态规划是一种求解最优化问题的方法,如背包问题、最长公共子序列、斐波那契数列等。C++代码展示了如何使用二维数组存储中间状态,避免重复计算,实现问题的最优解。 7. **贪心算法**:贪心算法...

    活动安排问题 贪心法——C++代码

    6. **动态规划与贪心算法的区别**:虽然本题使用了贪心算法,但同时也可以思考如果使用动态规划来解决,两种方法在处理这类问题时的异同。 7. **错误处理**:考虑边界条件,比如没有活动、活动数量过大等情况,并...

    ES6的JavaScript算法思想实现之分而治之,动态规划,贪心算法和回溯算法 贪心算法和动态规划.pdf

    ES6的JavaScript算法思想实现之分而治之、动态规划、贪心算法和回溯算法 一、分而治之算法思想实现 分而治之算法是一种常用的算法思想,它将原问题分解为多个小问题,解决小问题,然后将小问题的解决方案组合起来...

    leetcode 平台题目实现代码

    - 解决局部最优解能导致全局最优解的问题,如活动选择问题。 10. **概率与统计**: - 蒙特卡洛模拟、动态规划与随机化算法结合。 这本书中的每个题目实现都是一个独立的实例,读者可以通过阅读代码和理解解题...

    程序员代码面试指南:IT名企算法与数据结构题目最优解-代码

    - **动态规划**:解决背包问题、最长公共子序列、矩阵链乘法等。 - **贪心算法**:用于求解最优解,如活动选择问题、霍夫曼编码等。 - **回溯与分支限界**:用于解决组合优化问题,如八皇后问题、N皇后问题、迷宫...

    acm代码程序资源-acm-icpc-master.zip

    - **动态规划**:经典问题如背包问题、最长公共子序列、最长递增子序列等详细解析和代码实现。 - **贪心算法**:涉及区间调度、活动选择、霍夫曼编码等问题的解决方案。 - **分治算法**:合并排序、快速排序、...

    dongtaiguihua.zip_动态规划_动态规划算法

    在“dongtaiguihua.zip”压缩包中,包含的“动态规划代码”很可能是不同动态规划算法的实现,这些代码可以帮助我们理解和应用这种算法。 动态规划的基本思想是自底向上或自顶向下地构建最优解。自底向上方法通常从...

    剑指Offer题目Java实现代码

    在《剑指Offer》中,数组经常被用来解决排序、查找、动态规划等问题。 - **链表**:链表是线性数据结构,每个元素(节点)包含数据和指向下一个节点的引用。在面试中,链表操作如反转、合并、查找等都是常见的题目...

    算法分析与设计课设(递归,归并,贪心,动态规划)文档+代码

    在C/C++中,贪心算法常用于解决背包问题、最小生成树(如Prim或Kruskal算法)和活动选择问题等。贪心算法并不总是能找到全局最优解,但对某些特定问题,如最短路径问题,它能提供有效的解决方案。 4. **动态规划**...

    算法导论部分实现代码Java版

    - **活动选择问题**:如霍尔的婚姻理论、区间调度问题。 - **网络流**:最大流量问题,如Ford-Fulkerson算法或Edmonds-Karp算法。 6. **回溯法**: - **八皇后问题**:在棋盘上放置八个皇后,使其互不攻击。 - ...

Global site tag (gtag.js) - Google Analytics