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

hao3100590

浏览: 131457 次
性别:
来自: 成都

最近访客更多访客>>

hjg8858

周大大

xiaochunping9987

daringyun

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法学习

搭桥问题叠箱子最大递增子序列动态规划

参考链接：

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