没有合适的资源?快使用搜索试试~ 我知道了~
(动态规划-分治法-贪心法-回溯法)算法练习题
需积分: 1 0 下载量 19 浏览量
2023-07-17
22:56:47
上传
评论
收藏 49KB DOCX 举报
温馨提示
试读
27页
(动态规划-分治法-贪心法-回溯法)算法练习题
资源推荐
资源详情
资源评论
目录
动态规划...............................................................................................................................................................1
矩阵连乘问题.............................................................................................................................................2
最优子结构性质: .......................................................................................................................................2
最长公共子序列: .......................................................................................................................................3
背包问题—贪心算法 ...............................................................................................................................4
背包问题—分支限界法...........................................................................................................................5
最大子段和 .................................................................................................................................................5
分治法....................................................................................................................................................................6
2.1 递归与分治法.....................................................................................................................................6
2.2 Fibonacci 数列 ....................................................................................................................................7
2.4 全排列问题 .........................................................................................................................................7
2.6 棋盘覆盖问题.....................................................................................................................................8
2.9 线性时间选择 ..................................................................................................................................10
循环赛日程表 ..........................................................................................................................................11
递归循环:...................................................................................................................................................12
贪心法 .................................................................................................................................................................15
活动安排问题 ..........................................................................................................................................15
多机调度问题 ..........................................................................................................................................15
纸币找零问题 ..........................................................................................................................................17
乘船问题....................................................................................................................................................18
回溯法 .................................................................................................................................................................19
搜索子集树...............................................................................................................................................19
搜索排列树...............................................................................................................................................19
装载问题....................................................................................................................................................19
0-1 背包问题回溯算法.......................................................................................................................21
限界函数 Bound()的实现 .....................................................................................................................21
图的 m 着色问题回溯算法..................................................................................................................22
检查相邻结点的着色是否一样的约束函数...........................................................................23
n 皇后问题回溯算法..............................................................................................................................23
检查当前皇后位置的约束函数 .................................................................................................23
旅行商问题(TSP 问题) ....................................................................................................................24
流水作业调度问题 .................................................................................................................................25
子集和问题回溯算法.............................................................................................................................26
动态规划
矩阵连乘问题
using namespace std;
const int N=7;
void MatrixChainOrder(int *p,int m[N][N],int s[N][N],int length) {
int n=length-1;
int l,i,j,k,q=0;
for(i=1;i<length;i++)
m[i][i]=0; //第一层子问题解
for(l=2;l<=n;l++){ // l=2 表示 2 个矩阵相乘,
for(i=1;i<=n-l+1;i++){
j=i+l-1; //j 为长度为 l 的矩阵链的末位,
m[i][j]=0x7fffffff; //设个较大的初值
for(k=i;k<=j-1;k++){ //k 从 i 到 j-1,以 k 为位置划分
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j]){
m[i][j]=q;
s[i][j]=k;
}
}
}
}
cout << m[1][N-1] << endl;
}
最优子结构性质:
void MinMax(int n,int i,int s,int j, int &minf, int &maxf)
{
int e[4];
int a=m[i][s][0],b=m[i][s][1],r=(i+s-1)%n+1,c=m[r][j-1][0],d=m[r][j-1][1];
if(op[r]=='t')
{
minf=a+c;maxf=b+d;
}
else
{
e[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;
minf=e[1];maxf=e[1];
for(int r=2;r<5;r++)
{
if(minf>e[r]) mixf=e[r];
if(maxf<e[r]) maxf=e[r];
}
}
}
void MinMax(int n,int i,int s,int j, int &minf, int &maxf)
{
int e[4];
int a=m[i][s][0],b=m[i][s][1],r=(i+s-1)%n+1,c=m[r][j-1][0],d=m[r][j-1][1];
if(op[r]=='t')
{
minf=a+c;maxf=b+d;
}
else
{
e[1]=a*c;e[2]=a*d;e[3]=b*c;e[4]=b*d;
minf=e[1];maxf=e[1];
for(int r=2;r<5;r++)
{
if(minf>e[r]) mixf=e[r];
if(maxf<e[r]) maxf=e[r];
}
}
}
最长公共子序列:
算法 4.5 计算最长公共子序列的动态规划算法
#define NUM 100
int c[NUM][NUM];
int b[NUM][NUM];
void LCSLength (int m, int n, const char x[],char y[])
{
int i,j;
//数组 c 的第 0 行、第 0 列置 0
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
//根据递推公式构造数组 c
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; } //←
}
}
算法 4.5 计算最长公共子序列的动态规划算法
void LCSLength (int m, int n, const char x[],char y[])
{
int i,j;
//数组 c 的第 0 行、第 0 列置 0
……;
//根据递推公式构造数组 c
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; } //←
}
}
算法 4.6 计算最长公共子序列的动态规划算法
void LCS(int i,int j,char x[])
{
if (i ==0 || j==0) return;
if (b[i][j]== 1){ LCS(i-1,j-1,x); printf("%c",x[i]); }
else if (b[i][j]== 2) LCS(i-1,j,x);
else LCS(i,j-1,x);
}
背包问题—贪心算法
void Knapsack(int n,float M,float v[],float w[],float x[])
{ Sort(n,v,w);
int i;
for (i=1;i<=n;i++) x[i]=0;
float c=M;
for (i=1;i<=n;i++) {
if (w[i]>c) break;
x[i]=1;
c-=w[i];
}
if (i<=n) x[i]=c/w[i]; }
背包问题—分支限界法
while (i != n+1) {// 非叶结点
// 检查当前扩展结点的左儿子结点
Typew wt = cw + w[i];
if (wt <= c) {// 左儿子结点为可行结点
if (cp+p[i] > bestp) bestp = cp+p[i];
AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);}
up = Bound(i+1);
// 检查当前扩展结点的右儿子结点
if (up >= bestp) // 右子树可能含最优解
AddLiveNode(up, cp, cw, false, i+1);
最大子段和
计算最大子段和的动态规划算法
#define NUM 1001
int a[NUM];
int MaxSum(int n)
{
int sum=0;
int b=0;
for (int i=1;i<=n;i++)
{
if (b>0) b+=a[i]; else b=a[i];
if (b>sum) sum=b; }
return sum;
}
计算最大子段和的动态规划算法的最优解
#define NUM 1001
int a[NUM];
int MaxSum(int n, int &besti, int &bestj)
剩余26页未读,继续阅读
资源评论
hide17
- 粉丝: 30
- 资源: 10
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功