- 浏览: 604296 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
一、数组的最大子段和问题:
给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。
当所给的整数均为负数时定义子段和为0,依此定义,所求的最大值为:
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如,当(a1,a2,a3,a4,a4,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为20。'
我们令一个数组b,b[j]表示前j个元素能组成的最大和。如果b[j-1]大于零,则不管a[j]的情况,b[j-1]都可以向正方向影响,因此可以将a[j]加在b[j-1]上。如果b[j-1]小于零,则不管a[j]再大, 都会产生负影响,因此我们还不如直接令b[j]=a[j]。
运行:
C:\test>java LargestSubsegmentSum
15
1 2 -1 1 3 2 -2 3 -1 5 -7 3 2 -2 -1
The largest sub-segment sum is(最大子段和是):13
C:\test>java LargestSubsegmentSum
6
-2 11 -4 13 -5 -2
The largest sub-segment sum is(最大子段和是):20
二、最大子矩阵问题
在一个矩阵里面找它的子矩阵,使得子矩阵中各元素数值之和到达最大。
再来看一下上面提到的最大子段和问题,令b[j]表示从a[0]~a[j]的最大子段和,b[j]的当前值只有两种情况,
(1) 最大子段一直连续到a[j]
(2) 以a[j]为起点的子段
由此我们得出b[j]的状态转移方程为:b[j]=max{b[j-1]+a[j],a[j]},
所求的最大子段和为max{b[j],0<=j<n}。进一步我们可以将b[]数组用一个变量代替。得出的算法如下:
public int maxSubArray(int n,int a[])
{
int b=0,sum=-10000000;
for(int i=0;i< n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
这里用到了动态规划。现在回到我们的最初的最大子矩阵的问题,这个问题与上面所提到的最大子断有什么联系呢?
假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵,如下所示(ari表示a[r][i],假设数组下标从1开始):
那么我们将从第r行到第k行的每一行中相同列的加起来,可以得到一个一维数组如下:
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
由此我们可以看出最后所求的就是此一维数组的最大子段和问题,到此我们已经将问题转化为上面的已经解决了的问题了。
运行:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
15
下载源码
给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。
当所给的整数均为负数时定义子段和为0,依此定义,所求的最大值为:
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如,当(a1,a2,a3,a4,a4,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为20。'
我们令一个数组b,b[j]表示前j个元素能组成的最大和。如果b[j-1]大于零,则不管a[j]的情况,b[j-1]都可以向正方向影响,因此可以将a[j]加在b[j-1]上。如果b[j-1]小于零,则不管a[j]再大, 都会产生负影响,因此我们还不如直接令b[j]=a[j]。
import java.util.*; public class LargestSubsegmentSum { public static void main(String[] args) { /** *从键盘输入所要求的序列的长度n */ Scanner in=new Scanner(System.in); int n=in.nextInt(); /** *从键盘输入所要求的序列,存储在a[n]中 */ int[] a=new int[n]; int i; for(i=0;i< n;i++) { a[i]=in.nextInt(); } /** *求解最大子段和存在maxSum中 */ int maxSum=0; /* 我们令一个数组b,b[j]表示前j个元素能组成的最大和。如果b[j-1]大于零,则不管a[j]的情况, * b[j-1]都可以向正方向影响,因此可以将a[j]加在b[j-1]上。如果b[j-1]小于零,则不管a[j]再大, * 都会产生负影响,因此我们还不如直接令b[j]=a[j]。 */ int[] b=new int[n]; b[0]=a[0]; for(int j=1;j< n;j++) { if(b[j-1]>0){ b[j]=b[j-1]+a[j]; } else { b[j]=a[j]; } if(b[j]>maxSum) maxSum=b[j]; } System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum); } }
运行:
C:\test>java LargestSubsegmentSum
15
1 2 -1 1 3 2 -2 3 -1 5 -7 3 2 -2 -1
The largest sub-segment sum is(最大子段和是):13
C:\test>java LargestSubsegmentSum
6
-2 11 -4 13 -5 -2
The largest sub-segment sum is(最大子段和是):20
二、最大子矩阵问题
在一个矩阵里面找它的子矩阵,使得子矩阵中各元素数值之和到达最大。
再来看一下上面提到的最大子段和问题,令b[j]表示从a[0]~a[j]的最大子段和,b[j]的当前值只有两种情况,
(1) 最大子段一直连续到a[j]
(2) 以a[j]为起点的子段
由此我们得出b[j]的状态转移方程为:b[j]=max{b[j-1]+a[j],a[j]},
所求的最大子段和为max{b[j],0<=j<n}。进一步我们可以将b[]数组用一个变量代替。得出的算法如下:
public int maxSubArray(int n,int a[])
{
int b=0,sum=-10000000;
for(int i=0;i< n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
这里用到了动态规划。现在回到我们的最初的最大子矩阵的问题,这个问题与上面所提到的最大子断有什么联系呢?
假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵,如下所示(ari表示a[r][i],假设数组下标从1开始):
那么我们将从第r行到第k行的每一行中相同列的加起来,可以得到一个一维数组如下:
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
由此我们可以看出最后所求的就是此一维数组的最大子段和问题,到此我们已经将问题转化为上面的已经解决了的问题了。
import java.util.Scanner; public class Main { private int maxSubArray(int n,int a[]) { int b=0,sum=-10000000; for(int i=0;i< n;i++) { if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } return sum; } private int maxSubMatrix(int n,int[][] array) { int i,j,k,max=0,sum=-100000000; int b[]=new int[101]; for(i=0;i< n;i++) { for(k=0;k< n;k++)//初始化b[] { b[k]=0; } for(j=i;j< n;j++)//把第i行到第j行相加,对每一次相加求出最大值 { for(k=0;k< n;k++) { b[k]+=array[j][k]; } max=maxSubArray(k,b); if(max>sum) { sum=max; } } } return sum; } public static void main(String args[]) { Main p=new Main(); Scanner cin=new Scanner(System.in); int n=0; int[][] array=new int[101][101]; while(cin.hasNext()) { n=cin.nextInt(); for(int i=0;i< n;i++) { for(int j=0;j< n;j++) { array[i][j]=cin.nextInt(); } } System.out.println(p.maxSubMatrix(n,array)); } } }
运行:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
15
下载源码
发表评论
-
龙抬头
2014-11-10 15:06 632... -
求推箱子的最小步数(java)
2014-05-06 08:32 3776题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3337回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1848一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1248一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2030先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2316一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2270继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4984深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1445如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1169例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1505广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1675有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2131再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2280凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1112最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ...
相关推荐
标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...
在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...
在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...
标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...
在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...
在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...
在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...
动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...
在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...
三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...
在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...
动态规划算法以其卓越的能力,成为应对这类问题的首选工具。它通过把复杂问题分解成更小、更易于管理的子问题,以递归的方式进行解决。这种方法不仅效率高,而且在很多情况下比其他算法(如贪婪算法或分治算法)更优...
在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...
标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...
**算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...
动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...
"基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...
本资源包含的100例算法涵盖了排序、搜索、图论、动态规划、递归等多个重要类别。 1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法是数据处理的基础,用于将一组无序的...