简单算法记录

前言

最近在刷oj,感觉自己菜的抠脚,算法也不是很熟悉,需要加强一下,正好也为了后面的oj测试准备一下

动态规划

最长公共子序列

题目描述
给你一个序列X和另一个序列Z,当Z中的所有元素都在X中存在,并且在X中的下标顺序是严格递增的,那么就把Z叫做X的子序列。
例如:Z=是序列X=的一个子序列,Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y,请问它们的最长公共子序列的长度是多少?

输入
输入包含多组测试数据。每组输入占一行,为两个字符串,由若干个空格分隔。每个字符串的长度不超过100。

输出
对于每组输入,输出两个字符串的最长公共子序列的长度。

最长公共子序列问题,递推公式为

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
#include<iostream>
#include<string>
using namespace std;
string x;
string y;
int b[105][105],c[105][105];
void LCSLength(int m, int n){
for(int i=0;i<=m;i++) c[i][0] = 0;
for(int i=0;i<=n;i++) c[0][i] = 0;
for(int i=0;i<m;i++)
for(int j=0;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 traceback(int i,int j){
if(i==-1||j==-1) return;
if(b[i][j]==1){
cout<<x[i];
traceback(i-1,j-1);
}
else if(b[i][j]==2) traceback(i-1,j);
else traceback(i,j-1);
}
int main(){
while(cin>>x>>y){
int a = x.length();
int b = y.length();
LCSLength(a,b);
cout<<c[a-1][b-1]<<endl;
traceback(a-1, b-1);
cout<<endl;
}
return 0;
}

最大字段和

题目描述
给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj(子段可为空集)的最大值。

输入
包含多组测试数据。第一行为一个整数T(1<=T<=20),代表测试数据个数。
每组测试数据第一行为一个整数n,代表有n个整数(1<=n<=10000)。
接下来一行有n个数x(-1000<=x<=1000)。

输出
输出其对应的最大子段和。

递推公式

1
b[i] = max{b[i-1]+a[i], a[i]}  (1≤i≤n)
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
#include<iostream>
int num[10005];
using namespace std;
//再给出输出最优解的方法
int temp_start,len;
int besti,bestj;
void get_res(){
for(int i=besti;i<bestj;i++){
cout<<num[i]<<" ";
}
cout<<endl;
}
int main(){
int t,n;
int b = 0;
int ans =0;
cin>>t;
while(t>0){
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
temp_start = 0;
len = 1;
for(int i=0;i<n;i++){
if(b>0){
b = b + num[i];
len++;
}else{
b = num[i];
temp_start = i;
len = 1;
}
if(ans < b){
ans = b;
besti = temp_start;
bestj = temp_start + len;
}
}
cout<<ans<<endl;
//get_res();
t--;
}
return 0;
}

矩阵连乘

待续

0-1背包

题目描述
已知有N种物品和一个可容纳C重量的背包。每种物品i的重量为Wi,价值为Pi。那么,采用怎样的装包方法才会使装入背包物品的总价值最大。

输入
包含多组测试数据。第一行为一个整数T(1<=T<=10),代表测试数据个数。

接下来有T组测试数据。每组测试数据第一行为背包的重量C(C<10000)和物品个数N(N<1000)。接下来的N行分别为物品的重量cost(1<=cost<=100)和价值val(1<=val<=3000000)。(注意:结果可能超过int范围)

输出
对每组测试数据,输出其对应的所装物品的最大价值。

递推公式

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<algorithm>
using namespace std;
int c,n;
int x[1005];
long w[1005];
long v[1005];
long long m[1005][10005];//数组长度要开的合适一点
void pack(){
for(int i=0;i<w[n];i++) m[n][i] = 0;
for(int i=w[n];i<=c;i++) m[n][i] = v[n];
for(int i=n-1;i>0;i--){
for(int j=0;j<w[i];j++) m[i][j] = m[i+1][j];
for(int j=w[i];j<=c;j++){
m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
}
}
//利用m的下标的意义来构造最优解
void traceback(){
for(int i=1;i<=n;i++){
if(m[i][c]!=m[i+1][c]){
cout<<i<<" ";
c -= w[i];
}
}
cout<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>c>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
pack();
cout<<m[1][c]<<endl;
//traceback();
}
return 0;
}
-------------本文结束感谢您的阅读-------------
您今天怎么辣么迷人!