昨天对活动选择的动态规划解做了分析和描述,今天就来简单的实现一下代码,并用实例来验证其运行的正确性。
//基础类用来保存动态的集合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]
分享到:
相关推荐
动态规划是另一种解决会议安排问题的方法,思路是将活动按结束时间递增排序,然后使用动态规划表dp[i]记录活动i为结尾的最大的活动安排数。如果活动i可以被安排上,则dp[i]=dp[i-1]+1,否则dp[i]=dp[i-1]。最后,...
标题中的"acm基础之--acm常用代码1"表明这是一份针对ACM编程初学者的资源,可能包含了一些基本的算法和代码实现。 描述中提到这是一个“网页文件”,这意味着它可能是一个集合了各种代码示例的在线文档,便于阅读和...
在"Activity_Selection"这个压缩包中,可能包含了关于活动选择问题的更多实例、代码实现、复杂度分析或其他相关材料。通过深入学习和实践这些内容,我们可以更好地理解和掌握活动选择问题的算法设计与分析方法,以及...
《代码随想录》是一本深受程序员喜爱的编程学习资料,尤其在算法领域,它提供了丰富的实例和深入的解析,帮助读者理解并掌握动态规划、回溯、递归、二叉树以及贪心等核心算法。这些算法是解决复杂计算问题的基础工具...
综上所述,MDL-Matlab代码.rar提供的MATLAB代码实现了最小完成时间算法,用于解决任务调度问题。通过理解和分析这些代码,我们可以学习如何在实际应用中使用动态规划、贪心策略或启发式方法来优化任务的完成时间。...
4. **动态规划**:动态规划是一种解决最优化问题的策略,通过将大问题分解为子问题来求解。书中可能包含背包问题、最长公共子序列、斐波那契数列等经典例子。 5. **贪心算法**:贪心算法在每一步选择局部最优解,...
- 探索动态规划和贪心算法的区别,理解何时贪心策略适用,何时需要更全面的动态规划方法。 - 学习并练习使用C++ STL的高级特性,如迭代器、函数对象和模板元编程,以提高代码效率和可读性。 总之,这个压缩包提供...
"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] >= f[j]) { a[i] = true; j = i; count++; } else...
6. **动态规划**:动态规划是一种求解最优化问题的方法,如背包问题、最长公共子序列、斐波那契数列等。C++代码展示了如何使用二维数组存储中间状态,避免重复计算,实现问题的最优解。 7. **贪心算法**:贪心算法...
6. **动态规划与贪心算法的区别**:虽然本题使用了贪心算法,但同时也可以思考如果使用动态规划来解决,两种方法在处理这类问题时的异同。 7. **错误处理**:考虑边界条件,比如没有活动、活动数量过大等情况,并...
ES6的JavaScript算法思想实现之分而治之、动态规划、贪心算法和回溯算法 一、分而治之算法思想实现 分而治之算法是一种常用的算法思想,它将原问题分解为多个小问题,解决小问题,然后将小问题的解决方案组合起来...
- 解决局部最优解能导致全局最优解的问题,如活动选择问题。 10. **概率与统计**: - 蒙特卡洛模拟、动态规划与随机化算法结合。 这本书中的每个题目实现都是一个独立的实例,读者可以通过阅读代码和理解解题...
- **动态规划**:解决背包问题、最长公共子序列、矩阵链乘法等。 - **贪心算法**:用于求解最优解,如活动选择问题、霍夫曼编码等。 - **回溯与分支限界**:用于解决组合优化问题,如八皇后问题、N皇后问题、迷宫...
- **动态规划**:经典问题如背包问题、最长公共子序列、最长递增子序列等详细解析和代码实现。 - **贪心算法**:涉及区间调度、活动选择、霍夫曼编码等问题的解决方案。 - **分治算法**:合并排序、快速排序、...
在“dongtaiguihua.zip”压缩包中,包含的“动态规划代码”很可能是不同动态规划算法的实现,这些代码可以帮助我们理解和应用这种算法。 动态规划的基本思想是自底向上或自顶向下地构建最优解。自底向上方法通常从...
在《剑指Offer》中,数组经常被用来解决排序、查找、动态规划等问题。 - **链表**:链表是线性数据结构,每个元素(节点)包含数据和指向下一个节点的引用。在面试中,链表操作如反转、合并、查找等都是常见的题目...
在C/C++中,贪心算法常用于解决背包问题、最小生成树(如Prim或Kruskal算法)和活动选择问题等。贪心算法并不总是能找到全局最优解,但对某些特定问题,如最短路径问题,它能提供有效的解决方案。 4. **动态规划**...
- **活动选择问题**:如霍尔的婚姻理论、区间调度问题。 - **网络流**:最大流量问题,如Ford-Fulkerson算法或Edmonds-Karp算法。 6. **回溯法**: - **八皇后问题**:在棋盘上放置八个皇后,使其互不攻击。 - ...