《趣学算法》第四章 动态规划源代码

标签：相关   遍历   字符   不用   std   ade   max   规模   绝对值   

动态规划相关代码实现：

1、孩子有多像爸爸——最长的公共子序列

//program 4-1
#include 
#include
using namespace std;
const int N=1002;
int c[N][N],b[N][N];
char s1[N],s2[N];
int len1,len2;

void LCSL()
{
    int i,j;
    for(i = 1;i =c[i-1][j])
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 3;
            }
        }
     }
}

void print(int i, int j)//根据记录下来的信息构造最长公共子序列（从b[i][j]开始递推）
{
    if(i==0 || j==0) return;
    if(b[i][j]==1)
    {
        print(i-1,j-1);
        cout> s1;
    cout > s2;
    len1 = strlen(s1);//计算两个字符串的长度
    len2 = strlen(s2);
    for(i = 0;i 

2、DNA基因鉴定——编辑距离

//program 4-2
#include 
#include 
using namespace std;
const int N=100;
char str1[N],str2[N];
int d[N][N]; //定义辅助数组，d[i][j]表示str1前i个字符和str2前j个字符的编辑距离。

int min(int a, int b)
{
    return a> str1;
    cout > str2;
    cout 

3、长江一日游——游艇租赁

//program 4-3
#include
using namespace std;
const int ms = 1000;
int r[ms][ms],m[ms][ms],s[ms][ms];    //i到j站的租金
int n;            //共有n个站点
void rent()
{
    int i,j,k,d;
    for(d=3;d> n;
    cout >r[i][j];
            m[i][j]=r[i][j];
        }
    rent();
    cout 

4、快速计算——矩阵连乘

//program 4-4
#include
#include
#include
using namespace std;
const int msize = 100;
int p[msize];
int m[msize][msize];
int s[msize][msize];
int n;

void matrixchain()
{
    int i,j,r,k;
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    for(r = 2; r > n;
    int i ,j;
    cout > p[i];
    matrixchain();
    print(1,n);
    cout 

5、切呀切皮萨——最优三角剖分

//program 4-5
#include
#include
#include
#include
#include
using namespace std  ;
const int M= 1000 + 5 ;
int n ;
int s[M][M] ;
double m[M][M],g[M][M];
void  Convexpolygontriangulation()
{
    for(int i = 1 ;i  temp)
              {
                  m[i][j] = temp ;   // 更新最优值
                  s[i][j] = k ;      // 记录中间点
              }
          }
      }
}
void print(int i , int j)  // 输出所有的弦
{
    if(i == j)  return ;
    if(s[i][j]>i)
      couts[i][j]+1)
      cout> n;
    n-- ;
    cout >g[i][j] ;
    Convexpolygontriangulation();
    cout

6、小石子游戏——石子合并

//program 4-6
#include 
#include 
using namespace std;

const int INF = 1 max_Circular)
           max_Circular=Max[i][n+i-1];
    }
}

int main()
{
    int n;
    cout > n;
    cout >a[i];
    straight(a, n);
    cout

//program 4-6-1
#include 
#include 
using namespace std;

const int INF = 1 i?s[i][j-1]:i;
            int j1=s[i+1][j]Max[i][j-1])
               Max[i][j]=Max[i+1][j]+tmp;
            else
               Max[i][j]=Max[i][j-1]+tmp;
        }
    }
}

void straight(int a[],int n)
{
    for(int i=1;imax_Circular)
           max_Circular=Max[i][n+i-1];
    }
}

int main()
{
    int n;
    cout > n;
    cout >a[i];
    straight(a, n);
    cout

7、大卖场购物车1——0-1背包问题

//program 4-7
#include 
#include
#include
using namespace std;
#define maxn 10005
#define M 105
int c[M][maxn];//c[i][j] 表示前i个物品放入容量为j购物车获得的最大价值
int w[M],v[M];//w[i] 表示第i个物品的重量，v[i] 表示第i个物品的价值
int x[M];  //x[i]表示第i个物品是否放入购物车
int main(){
    int i,j,n,W;//n表示n个物品，W表示购物车的容量
    cout > n;
    cout > W;
    cout >w[i]>>v[i];
    for(i=1;i0;i--)
        if(c[i][j]>c[i-1][j])
        {
            x[i]=1;
            j-=w[i];
        }
        else
            x[i]=0;
    cout

//program 4-7
#include 
#include
using namespace std;
#define maxn 10005
#define M 105
int dp[maxn];//dp[j] 表示当前已放入容量为j的购物车获得的最大价值
int w[M],v[M];//w[i] 表示第i个物品的重量，v[i] 表示第i个物品的价值
int x[M];  //x[i]表示第i个物品是否放入购物车
int i,j,n,W;//n表示n个物品，W表示购物车的容量
void opt1(int n,int W)
{
     for(i=1;i0;j--)
            if(j>=w[i])  //当物品的重量大于购物车的容量，比较此物品放与不放是否能使得购物车内的价值最大
              dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}

void opt2(int n,int W)
{
     for(i=1;i=w[i];j--)
            //当物品的重量大于购物车的容量，比较此物品放与不放是否能使得购物车内的价值最大
           dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}

void opt3(int n,int W)
{
     int sum[n];//sum[i]表示从1...i的物品重量之和
     sum[0]=0;
     for(i=1;i=bound;j--)
            //当物品的重量大于购物车的容量，比较此物品放与不放是否能使得购物车内的价值最大
           dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
     }
}

int main()
{
    cout > n;
    cout > W;
    cout >w[i]>>v[i];
    for(j=1;j0;i--)
    {
        while(dp[j]==dp[j-1])
            j--;
        if(dp[j]

8、快速定位——最优二叉搜索树

//program 4-8
#include
#include   //求绝对值函数需要引入该头文件
using namespace std;
const int M=1000+5;
double c[M][M],w[M][M],p[M],q[M];
int s[M][M];
int n,i,j,k;
void Optimal_BST()
{
	for(i=1;i1E-6)//C++中浮点数因为精度问题不可以直接比较
				{
					c[i][j]=temp;
					s[i][j]=k;//k即为从下标i到j的根节点
				}
			}
			c[i][j]+=w[i][j];
		}
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
	if(flag==0)
	{
		cout=j)
	{
		cout> n;
    cout>p[i];
    cout >q[i];
	Optimal_BST();
	// /*用于测试
	for(i=1; i

//program 4-8-1
#include
#include   //求绝对值函数需要引入该头文件
using namespace std;
const int M=1000+5;
double c[M][M],w[M][M],p[M],q[M];
int s[M][M];
int n,i,j,k;
void Optimal_BST()
{
	for(i=1;ii?s[i][j-1]:i;
            int j1=s[i+1][j]1E-6)//C++中浮点数因为精度问题不可以直接比较
				{
					c[i][j]=temp;
					s[i][j]=k;//k即为从下标i到j的根节点
				}
			}
			c[i][j]+=w[i][j];
		}
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
	if(flag==0)
	{
		cout=j)
	{
		cout> n;
    cout>p[i];
    cout >q[i];
	Optimal_BST();
	// /*用于测试
	for(i=1; i

《趣学算法》第四章 动态规划源代码

标签：相关   遍历   字符   不用   std   ade   max   规模   绝对值   

原文地址：https://www.cnblogs.com/self-confidence/p/13604463.html