- 浏览: 128727 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
参考链接:
a.http://www.programfan.com/blog/article.asp?id=13086
b.http://blog.csdn.net/hhygcy/article/details/3950158
1.对(http://hao3100590.iteye.com/blog/1548135)中问题6:最长递增子序列的改进,减少时间复杂度
算法的思想:
它不是使用的动态规划法,而是普通的算法思想,就是在数组中直接存储最长递增子序列,在循环的过程中不断的查找插入位置,直到最终找到。下面列出实现的过程:
从上面的过程可以看出该算法的实现过程,在查找sub合适插入位置的时候,使用了二分查找,提高了查找速度,这个算法本身也比前面利用动态规划法简单,但是该算法复杂之处不在算法
而在算法正确性的证明!,算法证明见:http://www.programfan.com/blog/article.asp?id=13086
代码:
#include <iostream> #include <cstring> using namespace std; const int MIN = -32768; /** *a :原始数组 *sub :最终获取的最大递增子序列(注意,sub[0]是哨兵,结果从1开始) *length :数组长度 **/ int longestSub(int* a, int* sub, int length){ if(length<=0) return 0; sub[0]=MIN; //为了初始化的比较,相当于哨兵的作用 sub[1]=a[0]; //初始序列就是a[0] int len = 1; //最大递增子序列长度 int mid, left, right; //二分查找时的index for(int i=0; i<length; i++){ //在sub数组中二分查找合适的插入位置 left = 0; right = len; //获取的最终插入位置就如a[i]=6,{1,3,5,7}位置就是5后面index=3,会替代7 while(left<=right){ mid = (left+right)/2; if(sub[mid]<a[i]) left=mid+1; else right=mid-1; } //策略是使用替代,不断的寻找合适的值,插入sub,最后sub中剩余的值就是要寻找的最长递增子序列 sub[left]=a[i]; if(left>len) len++; } return len; } int main(){ int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }; int* sub = new int[13]; memset(sub,0,sizeof(int)); int length = longestSub(a,sub,13); cout<<"length:"<<length<<endl; for(int i=1; i<=length; i++) cout<<sub[i]<<" "; delete[] sub; sub=NULL; return 0; }
这个算法的时间复杂度只有O(nlogn),效率明显提高了而且也更简单了
不过其结果和改进之前的有些不同,前面是{1,3,4,5,6,19},改进之后是{1,3,4,5,6,7}结果都是正确的!
2.实际应用的两个例子
a.造桥问题
问题描述:
要在一条河的南北两边的各个城市之间造若干座桥.桥两边的城市分别是a(1)...a(n)和b(1)...b(n).这里的要求a(i)只可以和b(i)之间造桥,同时两座桥之间不能交叉.希望可以得到一个尽量多座桥的方案.
问题分析:
首先,这是一个动态规划的问题,即解答有许多中,寻找一个最优的解决方案。
其次,问题抽象,就是怎样将这个问题抽象成一个数学模型进行解决
第一步:就是搞清楚问题是什么?-------就是对号入座A对应于B的序号,这样的解决方案有许多如1,5,4和2,5,4以及1,3
第二步:抽象-------抽象成两个数组S1(1,2,5,4,3), S2(2,1,3,5,4),然后找S1和S2中相同的数字,且序号必须在数组下标递增,找出最多的对数
(即S1中的1对应了S2中的1,S1中的2对应了S2中的2,虽然S1中的下标是1,2 但是在S2中的下标是2,1没有递增,故而是不行的---更简单的说就是上面图不能交叉)
第三步:找规律--------这是最难的,如何才能从中找到突破口,我们在寻找的过程中发现,联系S1和S2的桥梁是什么?就是组成对的两个数在各自数组中的下标
那我们把这些下标都写出来,只是写一方就可以了从S1到S2的,就设为S3(2,1,4,5,3)---就表示S3[0]=2表示S1数组第一个值对应与S2中的第二个值(这个2就是在S2中的下标),
从而依次就把S3写出来了,这样找对数最多,而S3表示的是连线时对方的下标,那么是不是只要下标递增就不会交叉了?事实就是这样!!
就是找S3中的最长递增数组,这里就是{2,4,5}或者{1,4,5}
第四步:写代码-------既然突破口找到了,代码就不是问题了
代码
/** *建桥问题 **/ #include <iostream> #include <cstring> using namespace std; /** *建立建桥索引数组 *a : 原始数组a *b : 原始数组b *c :建立的索引数组 *length :数组长度 */ void build(const int* a, const int* b, int* c, int length){ for(int i=0; i<length; i++){ for(int j=0; j<length; j++){ if(a[i]==b[j]){ c[i]=j+1;//我们建立数组时以1为开始 break; } } } } /** *s2 :原始数组S2 *rt : 求出的最大递增子序列 *length:数组长度 */ void printResult(int* s2, int* rt, int length){ int j = 0; for(int i=0; i<length; i++) { if(rt[i]==0) break; j = s2[rt[i]-1]; cout<<"B"<<j<<"--A"<<j<<" "; } cout<<endl; } /** *a : 原始数组 *length :数组长度 *sub :求出的最大递增子序列 */ void longestIncreaseSub(int* a, int length, int* sub){ int n = length; int *t = new int[n]; int *p = new int[n]; memset(p,0,sizeof(int)); t[0]=1; for(int i=1; i<n; i++){ t[i]=1; for(int j=0; j<i; j++){ if(a[j]<a[i] && t[j]>t[i]-1){ t[i]=t[j]+1; p[i]=j; } } } int m=0,k=0; for (int i=1;i<=n;i++) { if (m<t[i]) { m = t[i]; k = i; } } while(m>=0){ sub[m-1] = a[k]; m--; k = p[k]; } delete[] t; delete[] p; p = NULL; t = NULL; } int main(){ int a[] = {1,2,5,4,3}; int b[] = {2,1,3,5,4}; int length = sizeof(a)/sizeof(int); //索引数组 int* c = new int[length]; //存储最终结果 int* sub = new int[length]; memset(sub,0,sizeof(int));//初始化sub memset(sub,0,sizeof(int));//初始化sub build(a,b,c,length); longestIncreaseSub(c,length, sub); printResult(b,sub, length); delete[] c; delete[] sub; c = NULL; sub = NULL; return 0; }
b.叠箱子问题
问题描述:
1.一排有许多不同的箱子,长宽高不一样
2.你需要把他叠放的尽量的高.但是箱子的摆放必须满足大的在下面,小的在上面的原则
3.箱子可以任意旋转(这就意味着你要用一个箱子的时候,旋转到合适位置)
问题分析:
具体分析见图:
注1:盒子要比上面的大--准确的说,是Wi>Wj && Di>Dj,单独使用Si>Sj不准确,因为可能很长但很窄,不和题目要求
为了满足要求,我们人为规定,W<=D(输入时确定或者后来处理),这样就不用担心这个问题了,使用Si>Sj就满足要求。
注2:记住盒子可以旋转,意味着每个盒子可以有三个面可以使用,旋转数量不限。
注3:本体关键是建立模型,列出动态规划的方程
代码:
/** * *叠箱子问题 */ #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; //定义一个箱子结构体 struct Box{ int h;//高 int w;//宽 int d;//长 }; //排序比较器 bool boxCompare(const Box& a, const Box&b){ return a.d*a.w > b.d*b.w;//降序排序 } //最高的堆叠高度算法 int highestBox(const vector<Box>& b){ //初始判断 if(b.size()<=0) return 0; //初始化一个vector,长度是原来的三倍,因为每个箱子都有三种翻转方式,每种当成一个新的箱子 vector<Box> boxs(b.size()*3); //箱子的处理,使所有的箱子都是w<=d,每个箱子都翻转两次 for(int i=0; i<b.size(); i++){ //下面是一个箱子的三种翻转情况 boxs[i*3+0].h = b[i].h; boxs[i*3+0].w = b[i].w < b[i].d ? b[i].w : b[i].d; boxs[i*3+0].d = b[i].w < b[i].d ? b[i].d : b[i].w; boxs[i*3+1].h = b[i].h; boxs[i*3+1].w = b[i].h < b[i].d ? b[i].h : b[i].d; boxs[i*3+1].d = b[i].h < b[i].d ? b[i].d : b[i].h; boxs[i*3+2].h = b[i].h; boxs[i*3+2].w = b[i].w < b[i].h ? b[i].w : b[i].h; boxs[i*3+2].d = b[i].w < b[i].h ? b[i].h : b[i].w; } //排序(不是boxCompare()) sort(boxs.begin(), boxs.end(), boxCompare); //最长递增子序列问题 vector <int> m(b.size()*3); m[0] = boxs[0].h; for(int i=0; i<boxs.size(); i++){ for(int j=0; j<i; j++){ if ( (boxs[i].w <= boxs[j].w) && (boxs[i].d <= boxs[j].d) && (m[i] < m[j]+boxs[i].h) ) m[i] = m[j]+boxs[i].h; } } int mm = *max_element(m.begin(),m.end()); return mm; } int main(){ vector<Box> box(3); box[0].h = 2; box[0].w = 3; box[0].d = 4; box[1].h = 2; box[1].w = 3; box[1].d = 1; box[2].h = 5; box[2].w = 3; box[2].d = 4; cout<<highestBox(box)<<endl; return 0; }
发表评论
-
排序方法总结
2012-08-12 11:34 1133这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14221.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11741.堆的概念 这里只需要注意两点: a.堆的存储方式:就是 ... -
set和map的简单实现
2012-08-10 11:35 12771.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9101.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15891.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27961.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14191.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56131.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11891.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12381.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25581.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14941.算法描述 a.数据结构与算法(Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10761.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17551.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12901.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9551.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
线性查找二维数组
2012-06-05 17:23 10011.算法描述 有序(行有序,列有序,且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2233算法描述:生成前N个整 ...
相关推荐
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
动态规划适用于多种实际应用场景,例如最短路径问题、背包问题、字符串匹配问题、最长公共子序列问题以及最长递增子序列问题等。在实际应用中,动态规划可以大大提高算法的性能,并找到问题的最优解。 总的来说,...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...