`
hao3100590
  • 浏览: 131244 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

关于最长递增子序列的实际应用--动态规划

阅读更多

参考链接:

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;
}
 

 

  • 大小: 7.5 KB
  • 大小: 17.5 KB
  • 大小: 6.4 KB
分享到:
评论

相关推荐

    动态规划:最长单调递增子序列

    ### 动态规划:最长单调递增子序列 在计算机科学和算法设计中,动态规划是一种重要的技术,用于解决...在实际应用中,最长单调递增子序列问题有着广泛的应用场景,如生物信息学中的基因排序、金融市场的趋势分析等。

    最长递增子序列 动态规划法.cpp.rar

    以下是动态规划解决最长递增子序列的步骤: 1. 初始化:创建一个长度为n(数组长度)的dp数组,所有元素都初始化为1。因为每个元素本身至少可以构成一个长度为1的递增子序列。 2. 遍历数组:对于数组中的每个元素...

    最长递增子序列问题

    最长递增子序列(Longest Increasing Subsequence, LIS)问题是计算机科学中的一种经典动态规划问题,广泛应用于算法设计和分析。在给定的整数序列中,我们的目标是找到一个尽可能长的、不降序的子序列。这个子序列...

    最长递增子序列java源码

    在本实验中,我们将探讨如何使用Java编程语言解决“最长递增子序列”(Longest Increasing Subsequence, LIS)的问题。这是一个经典的动态规划问题,在计算机科学和算法设计中具有广泛的应用,例如在股票交易策略、...

    最长递增子序列多种实现(java)

    最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一种经典的动态规划问题,广泛应用于算法竞赛和实际编程场景。在这个Java实现中,我们将深入探讨如何找到一个序列中长度最长的递增子序列。 ...

    最长递增子序列LCS的实现C源码

    最长递增子序列(Longest Increasing Subsequence, LCS)是计算机科学中一种经典的动态规划问题,常见于算法和数据结构的学习。在这个问题中,我们给定一个无序整数序列,目标是找到序列中的一个子序列,使得这个子...

    PTA丨最长连续递增子序列

    在这个例子中,`dp` 数组用于存储以每个元素结尾的最长递增子序列的长度,而 `max_len` 用于跟踪全局最长递增子序列的长度。时间复杂度为 O(n^2),空间复杂度为 O(n)。 了解了基本的动态规划解决方案后,还可以考虑...

    中科大算法导论课程实验 最长递增子序列 代码

    在本实验中,我们关注的是“最长递增子序列”(Longest Increasing Subsequence, LIS)这一经典问题,它是算法课程中的一个核心课题,尤其在动态规划的应用上有着重要的地位。中科大软件学院的这个实验旨在让学生...

    求取最长递增子序列(MFC编程)

    以上就是关于"求取最长递增子序列(MFC编程)"的知识点详解,包括贪心算法和动态规划的基本思想,以及如何在MFC环境下实现这一算法。通过学习和实践这些内容,你不仅可以掌握一种重要的算法,还能了解到如何在实际...

    求最长非递增子序列长度

    最长非递增子序列(Longest Non-Increasing Subsequence,简称LNIS)问题是一个经典的计算机科学问题,尤其在算法设计和分析领域具有重要意义。这个问题的目的是在给定的一个无序整数序列中找到一个子序列,这个子...

    最长递增子序列C程序

    总的来说,最长递增子序列问题是一个经典而实用的算法问题,通过C语言实现,能够加深对动态规划的理解,并提供了一个实际应用的例子。学习并掌握这个问题的解决方法,将对任何IT专业人员的技能树都有积极的补充。

    排序最长递增子序列红黑树

    标题中的“排序最长递增子序列红黑树”是指在数据结构和算法领域中的两个重要概念:排序和最长递增子序列(Longest Increasing Subsequence, LIS),以及它们与红黑树(Red-Black Tree)的关联。在这个场景中,我们...

    C#实现-动态规划-最长公共子序列-DPLCS

    在实际应用中,动态规划不仅在最长公共子序列问题上有广泛的应用,还可以用于解决其他多种问题,例如背包问题、最长递增子序列、最小编辑距离等。因此,理解和掌握动态规划是提升编程技能的关键步骤之一,尤其对于...

    最长单调递增子序列(O(n2)).rar_company7ne_最长单调递增子序列(动态规划法)

    在实际应用中,除了求长度,我们还可能需要找出具体的最长单调递增子序列。这可以通过回溯dp数组来实现,从dp数组的最大值开始,逆向查找对应的子序列。 总结来说,最长单调递增子序列问题可以通过动态规划法在O(n^...

    算法实验(整数划分、各类排序、最长递增子序列、幻方矩阵)

    本实验涵盖了几个重要的算法概念,包括整数划分、排序算法、最长递增子序列以及幻方矩阵。下面将逐一详细介绍这些知识点。 1. 整数划分: 整数划分是一个数学问题,它涉及将一个正整数n划分为若干个正整数的和,...

    求一个整数序列的最长递增子序列.doc

    第二个代码也使用了动态规划,但其遍历和更新过程稍有不同,主要体现在`for`循环的结构和如何找到最长递增子序列的元素。 在实际应用中,动态规划的O(n log n)解法更受青睐,因为它在处理大数据集时效率更高,不会...

    js代码-求最长递增子序列

    在JavaScript编程语言中,"求...总之,"js代码-求最长递增子序列"是一个利用动态规划解决的经典问题,其JavaScript实现包括初始化动态规划数组、双层循环更新最长递增子序列长度,以及回溯找到最长递增子序列的过程。

    最长递增子序列1

    最长递增子序列(LIS)是数组或序列中一个重要的概念,它的目标是找到一个序列的最长子序列,使得这个子序列中的元素是严格递增的。在给定的描述中,我们看到了三种不同的方法来求解LIS问题。 **方法一:动态规划...

    动态规划算法求解最长严格递增子序列的长度问题

    递归函数 `findLIS(prev_idx, current_idx)` 将计算以 `current_idx` 结束的最长递增子序列的长度,其中 `prev_idx` 是上一个元素的索引。如果 `prev_idx` 不存在或当前元素大于 `prev_idx` 中的元素,我们会尝试在 ...

    数据与算法——实验报告——数列递增子序列

    这篇实验报告主要探讨了在数据与算法领域...总的来说,这个实验报告详细展示了如何运用动态规划解决最长递增子序列问题,同时指出在实际操作中可能出现的挑战和改进方向,为读者提供了深入理解动态规划算法的一个实例。

Global site tag (gtag.js) - Google Analytics