nefu 算法课设-动态规划

128 阅读 0 评论 85 点赞

我是靠谱客的博主长情指甲油，这篇文章主要介绍nefu 算法课设-动态规划，现在分享给大家，希望可以做个参考。

递归与分治
动态规划
贪心算法
回溯算法

文章目录

- 1. 数字三角问题
- 2、最长公共子序列问题
- 3、日常购物
- 4、台阶问题

1. 数字三角问题

问题描述：给定一个由n行数字组成的数字三角形，如下图所示
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
如上图最大值为30=7+3+8+7+5

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf=0x7f7f7f7f;
const int N=1e3+5;
int a[N][N];
int dp[N][N][2]; // [0] 记录最值 ，[1] 记录 路线方向
/* 转移方程
*到达位置（i，j） 只能从 (i-1,j) 或 （i-1，j-1） 位置出发
*dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i-1][j-1]+a[i][j]);
*/
void pr(int x,int y) // 打印路线
{
if(x!=1)
{
if(dp[x][y][1]==1)
{
pr(x-1,y);
}
else pr(x-1,y-1);
}
printf("(%d,%d)n",x,y);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
memset(dp,0,sizeof(0));
dp[1][1][0]=a[1][1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(dp[i-1][j][0]+a[i][j]<=dp[i-1][j-1][0]+a[i][j])
{
dp[i][j][0]=dp[i-1][j-1][0]+a[i][j];
dp[i][j][1]=2;
}
else
{
dp[i][j][0]=dp[i-1][j][0]+a[i][j];
dp[i][j][1]=1;
}
}
}
int ans=-inf,id=0;
for(int i=1;i<=n;i++)
{
if(ans<dp[n][i][0])
{
id=i;
ans=dp[n][i][0];
}
}
printf("%dn",ans);
pr(n,id);
// 打印路线
return 0;
}
/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/

2、最长公共子序列问题

问题描述：给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
输入：
第1行：两个子序列的长度，m n
第2行：第1个子序列的各个元素（序列下标从1开始）
第3行：第2个子序列的各个元素（序列下标从1开始）
输出：
最长公共子序列
实例：
4 5 //m和n的值
abad //输入4个字符，下标从1开始
baade //输入5个字符，下标从1开始
输出：
aad

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int dp[N][N][2];
char s1[N],s2[N];
int main()
{
int n,m;
cin>>n>>m;
cin>>s1+1>>s2+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s1[i]==s2[j])
{
dp[i][j][0]=dp[i-1][j-1][0]+1;
dp[i][j][1]=1;
}
else
{
if(dp[i-1][j][0]>=dp[i][j-1][0])
{
dp[i][j][0]=dp[i-1][j][0];
dp[i][j][1]=3;
}
else
{
dp[i][j][0]=dp[i][j-1][0];
dp[i][j][1]=2;
}
}
}
}
string s;
int mx=dp[n][m][0];
// cout<<mx<<endl;
int x=n,y=m;
while(mx)
{
if(dp[x][y][1]==1)
{
s+=s1[x];
// printf("..%d %dn",x,y);
mx--;
x--,y--;
}
else
{
if(dp[x][y][1]==2)
{
y--;
}
else
if(dp[x][y][1]==3)
{
x--;
}
}
}
for(int i=s.size()-1;i>=0;i--)
{
cout<<s[i];
}
cout<<endl;
return 0;
}
/*
4 5
abad
baade
*/

3、日常购物

问题描述：小明今天很开心，因为在家买的新房子即将拿到钥匙。新房里面有一间他自己专用的、非常宽敞的房间。让他更高兴的是，他的母亲昨天对他说：“你的房间需要购买什么物品？怎么布置，你说了算，只要他们的价格总和不超过N元钱”。小明今天早上开始预算，但他想买太多的东西，肯定会超过母亲的N元限额。因此，他把对每件物品的渴望程度，分为5等级：用整数1->5表示，第5等表示最想要。他还从互联网上找到了每件商品（所有整数）的价格。他希望在不超过N元（可能等于N元）的情况下，将每件商品的价格与效益度的乘积的总和最大化.
设第j件物品的价格为p[j]，重要度为w[j]，其选中的k件商品，编号依次为j1，j2，……，jk，则所求的总和为：
p[j1]×w[j1]+p[j2]×w[j2]+ …+p[jk]×w[jk]。
请帮小明设计一个符合要求的购物清单。
其中N=2000,K=6
p[1]=200 w[1]=2
p[2]=300 w[2]=2
p[3]=600 w[3]=1
p[4]=400 w[4]=3
p[5]=1000 w[5]=4
p[6]=800 w[6]=5

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
typedef struct
{
int x,w;
}stu;
stu p[N];
long long
dp[N];
int main()
{
int n=2000,k=6;
for(int i=1;i<=k;i++)
{
scanf("%d %d",&p[i].x,&p[i].w);
}
for(int i=1;i<=k;i++)
{
for(int j=n;j>=p[i].x;j--)
{
dp[j]=max(dp[j],dp[j-p[i].x]+p[i].x*p[i].w);
}
}
printf("%dn",dp[n]);
return 0;
}
/*
200 2
300 2
600 1
400 3
1000 4
800 5
8400
*/

4、台阶问题

问题描述：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。
实际情况：给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include
<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
int a[N][N];
int dp[N][N];
// dp[i][j]=min(dp[i][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(dp,inf,sizeof(dp));
for(int i=0;i<=n;i++)
dp[i][0]=dp[0][i]=0;
dp[1][1]=a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i-1>=1)
dp[i][j]=min(dp[i][j],dp[i-1][j]+a[i][j]);
if(j-1>=1)
dp[i][j]=min(dp[i][j],dp[i][j-1]+a[i][j]);
}
printf("%dn",dp[n][n]);
return 0;
}
/*
4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
12
*/