1.钢条切割
//
// main.cpp
// pearls
//
// Created by YangKi on 16/03/06.
// Copyright © 2015年 YangKi. All rights reserved.
#include <cstdio>
#include <iostream>
using namespace std;
int price[11]={-1,1,5,8,9, 10,17,17,20, 24,30};
int r[11];//r[i] 表示长度为i的钢条的最大收益
int max(int a, int b)
{
return a>b? a:b;
}
///////////////////////////////////////////////////////////没有用动态规划的版本
int cut_1(int *p, int length)//计算长度为length的钢条的最大收益
{
if(length == 0) return 0;
int q=-1;
for (int i=1; i <= length; i++)
{
q=max(q, p[i]+cut_1(p, length-i) );
}
return q;
}
///////////////////////////////////////////////////////////自底向上的dp
int cut_2(int *p, int length)
{
for (int i=0; i < 11; i++)
{
r[i]=-1;
}
r[0]=0;
for (int i=1; i<11; i++)
{
int q=-1;
for (int j=1; j<=i; j++)
{
q=max(q, p[j] + r[i-j]);
}
r[i] = q;
}
return r[length];
}
///////////////////////////////////////////////////////////增加切割成本cost,课后第三题,自底向上的dp
int cut_3(int *p, int length, int cost)
{
for (int i=0; i < 11; i++)
{
r[i]=-1;
}
r[0]=0;
for (int i=1; i<11; i++)
{
int q=-1;
for (int j=1; j<i; j++)
{
q=max(q, p[j] + r[i-j] - cost);
}
q=max(q, p[i]);//不剪的情况
r[i] = q;
}
return r[length];
}
int main()
{
int i=0;
while (i<12)
{
r[i++]=-1;
}
printf("maxr: %d\n", cut_3(price, 10, 1));
return 0;
}
2.矩阵链乘法
//
// main.cpp
// pearls
//
// Created by YangKi on 16/03/06.
// Copyright © 2015年 YangKi. All rights reserved.
#include <cstdio>
#include <iostream>
using namespace std;
int p[7]={30, 35, 15, 5, 10, 20, 25};// 代表矩阵30X35，35X15....
int m[7][7];//m[i,j]表示矩阵链i...j最小的乘法次数
int s[7][7];//记录具体怎么安排
void print(int i, int j)//打印矩阵链i...j的括号分配
{
if(i==j) printf("A_%d", i);
else
{
printf("(");
print(i, s[i][j]);
print(s[i][j]+1, j);
printf(")");
}
}
int main()
{
int i=1;
while (i<7)
{
m[i][i]=0;
i++;
}
for (int i=1; i<=5; i++)// 一共进行i-1次
{
for (int j=1; (j+i) <= 6; j++)
{
//m[j][j+i]-->m[a][b]
int q=INT_MAX;
int a=j;
int b=j+i;
for (int k=a; k<b; k++)
{
int temp=m[a][k] + m[k+1][b] + p[a-1]*p[k]*p[b];
if(temp<q)
{
q=temp;
s[a][b]=k;
}
}
m[a][b]=q;
}
}
for (int i=1; i<=6; i++)
{
for (int j=1; j<=6; j++)
{
if(i<j)
{
printf("m[%d][%d]=%07d ", i, j, m[i][j]);
}
}
printf("\n");
}
print(1, 6);
return 0;
}
3.最长公共子序列
//
// main.cpp
// pearls
//
// Created by YangKi on 16/03/07.
// Copyright © 2015年 YangKi. All rights reserved.
#include <cstdio>
#include <iostream>
#define X_length 7
#define Y_length 6
using namespace std;
int X[X_length+1]={-1,1,2,3,2,4,1,2};
int Y[Y_length+1]={-1,2,4,3,1,2,1};
int c[X_length+1][Y_length+1];//c[i][j]表示长度为i的x与j的y之间的lcs长度
int s[X_length+1][Y_length+1];//记录具体怎么安排
//1->situation1 (x[i]==y[j], use c[i-1][y-1])
//2->situation2 (x[i]!=y[j], use c[i-1][j] )
//3->situation3 (x[i]!=y[j], use c[i][j-1] )
void lcs_length(int a, int b)//x1...xa 与 y1...yb 的lcs长度
{
for (int i=0; i<=X_length; i++)
c[i][0]=0;
for (int i=0; i<=Y_length; i++)
c[0][i]=0;
for (int i=1; i <= a; i++)
{
for (int j=1; j <= b; j++)
{
if (X[i]==Y[j])
{
c[i][j]=c[i-1][j-1]+1;
s[i][j]=1;
}
else
{
if (c[i-1][j] >= c[i][j-1])
{
c[i][j]=c[i-1][j];
s[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
s[i][j]=3;
}
}
}
}
printf("lcs: %d\n", c[a][b]);
return;
}
void print_path(int a, int b)
{
while (a!=0 && b!=0)
{
printf("c[%d][%d]=%d\n", a, b, c[a][b]);
if (s[a][b]==1)
{
a--;
b--;
}
else if (s[a][b]==2)
a--;
else
b--;
if(a==0 || b==0)
{
printf("c[%d][%d]=%d\n", a, b, c[a][b]);
break;
}
}
}
int main()
{
lcs_length(7, 6);
print_path(7, 6);
return 0;
}
1.只用2Xmin(m,n)个表项来替代c[ ][ ]的版本。
2.只用min(m,n)个表项来替代c[ ][ ]的版本。
以上两个优化比较简单
4.最长单调增长子序列
设置状态数组d[i],表示以s[i]这个元素结尾的最长的单调增长子序列的长度。
//
// main.cpp
// pearls
//
// Created by YangKi on 16/03/08.
// Copyright © 2015年 YangKi. All rights reserved.
#include <cstdio>
#include <iostream>
#define length 9
using namespace std;
int s[length]={2,4,3,5,1,7,6,9,8};
int d[length];
int predecessor[length];// 里面的数字是当前元素的前置元素的坐标
int max(int a, int b)
{
return a>b? a:b;
}
void print_seq(int index)
{
if (predecessor[index]<index)
print_seq(predecessor[index]);
printf("%d ", s[index]);
}
void lis_length(int n)
{
for (int i=0; i<length; i++)
predecessor[i]=i;
d[0]=1;
for (int i=1; i<length; i++)
{
int maax=1;
int temp;
for (int j=0; j<i; j++)
{
if (s[j]<s[i])
temp=d[j]+1;
else temp=1;
if(temp>maax)
{
maax=temp;
predecessor[i]=j;
}
}
d[i]=maax;
}
int maax=-1;
int tail;
for (int i=0; i<length; i++)
{
if (d[i]>maax)
{
maax=d[i];
tail=i;
}
}
print_seq(tail);
printf("\n");
return;
}
int main()
{
lis_length(length);
return 0;
}
5.最优二叉搜索树
//
// main.cpp
// pearls
//
// Created by YangKi on 16/03/10.
// Copyright © 2015年 YangKi. All rights reserved.
#include <cstdio>
#include <iostream>
#define keyNum 5 //the num of key
using namespace std;
double p[keyNum+1]={-1, 0.15, 0.1, 0.05, 0.1, 0.2}; // p1, ..., pn
double q[keyNum+1]={0.05, 0.1, 0.05, 0.05, 0.05, 0.1};// q0, q1, ..., qn
double e[keyNum+2][keyNum+2];
double w[keyNum+2][keyNum+2];
int root[keyNum+2][keyNum+2];
void optimal_bst()
{
for (int i=0; i <= keyNum; i++)
{
e[i+1][i] = q[i];
w[i+1][i] = q[i];
}
for (int i=1; i <= keyNum; i++)
{
for (int j=1; (i+j) <= keyNum+1; j++)
{
w[j][i+j-1] = w[j][i+j-1-1] + p[i+j-1] + q[i+j-1];
e[j][i+j-1] = 100.0;//e[j][i+j], 正无穷大
for (int r=j; r <= (i+j-1); r++)
{
double temp = e[j][r-1] + e[r+1][i+j-1] + w[j][i+j-1];
if (temp < e[j][i+j-1])
{
e[j][i+j-1] = temp;
root[j][i+j-1]=r;
}
}
}
}
return;
}
void PRINT_OPTIMAL_BST(int i,int j)
{
int Root = root[i][j];//当前根结点
if (i==1 && j==keyNum)
printf("k_%d为根\n", Root);
if (i==Root)
{//如果左子树是叶子
printf("d_%d为k_%d的左子树\n", i-1, Root);
}
else
{
printf("k_%d为k_%d的左子树\n", root[i][Root-1], Root);
PRINT_OPTIMAL_BST(i,Root-1);
}
if (j==Root)
{//如果右子树是叶子
printf("d_%d为k_%d的右子树\n", j, Root);
}
else
{
printf("k_%d为k_%d的右子树\n", root[Root+1][j], Root);
PRINT_OPTIMAL_BST(Root+1,j);
}
}
int main()
{
optimal_bst();
PRINT_OPTIMAL_BST(1, 5);
return 0;
}
