动态规划

动态规划常见题目解析：

分别为：

1.最长公共子序列

2.最大字段和

3.0-1背包问题

下面逐一描述：

1.最长公共子序列

题目描述：

例如对于X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},则序列{B,C,B,A}就是X和Y的最长公共子序列。

解法：

按照该思路的解法：

#include <iostream>
using namespace std;
//动态规划算法-最长公共子序列

//m,n代表数组x和y的长度，c[i][j]表示Xi和Yj的最长公共子序列的长度，
//b[i][j]记录c[i][j]是由哪一种子问题的解得到的
void LCSLength(int m,int n,char x[],char y[],int c[][7],int b[][7])
{
	int i,j;
	for (i=1;i<=m;i++) c[i][0]=0;
	for (i=1;i<=n;i++) c[0][i]=0;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			if (x[i]==y[j])//第一种解的情况
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;
			}else if (c[i-1][j]>=c[i][j-1])//第二种解的情况
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}else//第三种解的情况
			{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
		}
}

//构造最长子序列
void LCS(int i,int j,char x[],int b[][7])
{
	if (i==0 || j==0) return;
	if (b[i][j]==1)
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i]<<'\t';
	}else if (b[i][j]==2)
		LCS(i-1,j,x,b);
	else
		LCS(i,j-1,x,b);
}


int main()
{
	char x[]={'Z','A','B','C','B','D','A','B'};//长度为8
	char y[]={'Z','B','D','C','A','B','A'};//长度为7
	int c[8][7];
	int b[8][7];
	LCSLength(7,6,x,y,c,b);
	LCS(7,6,x,b);
	cout<<endl;
	return 0;
}

 

2.最大字段和

问题描述：给定n个整数（可能有负整数）组成的序列a1,a2,...,an,求ai...aj的最大值，0<=i,j<n,例如当数组为{-2,11,-4,13,-5,-2}时,最大字段和为11+(-4)+13=20.

解法描述：

 

#include <iostream>
using namespace std;
//解法一：时间复杂度为O(n^2)
//n表示数组的长度，besti和bestj分别表示大子段的起止位置
int MaxSum1(int n,int a[],int &besti,int &bestj)
{
	int sum=0;
	for (int i=0;i<n;i++)
	{
		int tempsum=0;
		for (int j=i;j<n;j++)
		{
			tempsum+=a[j];
			if (tempsum>sum)
			{
				sum=tempsum;
				besti=i;
				bestj=j;
			}
		}
	}
	return sum;
}
//解法二：时间复杂度为O(n)
int MaxSum2(int n,int a[],int &besti,int &bestj)
{
	int sum=0,b=0;
	for (int i=0;i<n;i++)
	{
		if (b>0)
		{
			b+=a[i];
			if (a[i]>=0)//最后一个数字肯定是非负数
				bestj=i;
		}
		else
		{
			b=a[i];
			besti=i;//第一个数字肯定也是非负数，但无需判断
		}
		if (b>sum)
			sum=b;
	}
	return sum;
}

int main()
{
	int arr[6]={-2,11,-4,13,-5,-2};
	int besti,bestj;
	//cout<<MaxSum1(6,arr,besti,bestj)<<endl;
	cout<<MaxSum2(6,arr,besti,bestj)<<endl;
	cout<<besti<<"---"<<bestj<<endl<<"最大字段和序列如下："<<endl;
	for (int i=besti;i<=bestj;i++)
	{
		cout<<arr[i]<<endl;
	}
	return 0;
}

3.0-1背包问题

问题描述：给定n种物品和一背包，物品i的重量是w[i]，其价值为v[i]背包的容量为c，问应如何选择放入背包的物品是背包的总价值最大？

说明：物品只有两种选择：放入背包和不放入背包。

解法1描述：（效率较低，有条件限制：背包重量必须为正整数）

 

#include <iostream>
#define min(x,y)((x)>(y)?y:x)
#define max(x,y)((x)<(y)?y:x)
using namespace std;

//动态规划-0-1背包问题

//n表示有n个物品，v[n]存储的是物品价值，w[n]存储的是物品重量
//m[i][j]表示背包容量为j，可选物品是i,i+1,...,n时背包问题的最优解
//m[i][j]的递归式如下：
//m[i][j] = 1.max{m[i+1,j],m[i+1,j-w[i]]+v[i]}	j>=w[i];
//			2.m[i+1,j]							0<=j<w[i]
//m[n][j] = 1.v[n]								j>=w[n];	
//			2.0									0<=j<w[n]
//递归式解释：i=n的情况不需要解释，很容易理解；对于i的情况，如果0<=j<w[i]，则i元素肯定不放在
//背包中，所以和m[i+1,j]是相等的，如果j>=w[i],也就是说i元素有放入背包的可能，如果不放入背包，和
//0<=j<w[i]的情况是一样的，即m[i+1,j]，如果放入背包，就是先要求出背包元素为i+1至n,背包重量为j-w[i]的
//最优解即m[i+1,j-w[i]]然后再加上v[i],最后比较这这两个值的最大值。
//说明：该算法结束之后，容易看出m[1][c]即为背包问题的最优解
//v,w中的元素是从0->n-1;m中的元素是从1->n。
void Knapsack(int v[],int w[],int c,int n,int m[][11])
{
	int i,j;
	//首先计算当i=n-1的时候背包的最优解
	int jMax=min(w[n-1],c);
	//下面的两个语句考虑到了最小值为w[n-1]或者是c的情况
	for (j=0;j<jMax;j++)//当j<jMax时，求相应的最优解
		m[n][j]=0;
	for (j=w[n-1];j<=c;j++)//当w[n-1]<=j<=c的时候，求相应的最优解，如果c<w[n-1]，不执行下面的语句，上面的语句已经求出最优解
		m[n][j]=v[n-1];

	//然后计算0<i<n-1时的最优解
	for (i=n-2;i>0;i--)
	{
		jMax=min(w[i],c);
		for (j=0;j<jMax;j++)
			m[i+1][j]=m[i+2][j];
		for (j=w[i];j<=c;j++)
			m[i+1][j]=max(m[i+2][j],m[i+2][j-w[i]]+v[i]);
	}

	//最后计算i=0时的最优解
	m[1][c]=m[2][c];
	if (c>=w[0])
		m[1][c]=max(m[2][c],m[2][c-w[0]]+v[0]);
}

//将最优解构造出来，放到数组x[]中
void Traceback(int m[][11],int w[],int c,int n,int x[])
{
	for (int i=1;i<n;i++)
	{
		if (m[i][c]==m[i+1][c])//说明i不在背包中
			x[i]=0;
		else//i在背包中
		{
			x[i]=1;
			c-=w[i-1];
		}
	}		
	x[n]=(m[n][c])>0?1:0;
}


int main()
{
	int w[]={2,2,6,5,4};
	int v[]={6,3,5,4,6};
	int c=10;
	int x[6];
	int m[6][11];
	Knapsack(v,w,c,5,m);
	Traceback(m,w,c,5,x);
	cout<<"最优解是："<<endl;
	for (int i=1;i<=5;i++)
		cout<<i<<":"<<x[i]<<endl;
	return 0;
}

 解法1描述：（效率提升）