算法分析与设计-动态规划、贪心算法

目录

第三章——动态规划

第四章——贪心算法 

---

第三章——动态规划

/*【问题描述】
使用动态规划算法解矩阵连乘问题，具体来说就是，依据其递归式自底向上的方式进行计算，在计算过程中，保存子问题答案，每个子问题只解决一次，在后面计算需要时只要简单查一下得到其结果，从而避免大量的重复计算，最终得到多项式时间的算法。
【输入形式】
在屏幕上输入第1个矩阵的行数和第1个矩阵到第n个矩阵的列数，各数间都以一个空格分隔。
【输出形式】
矩阵连乘A1,...,An的最少数乘次数和最优计算次序。
【样例1输入】
30 35 15 5 10 20 25
【样例1输出】
15125
((A1(A2A3))((A4A5)A6))
【样例说明】
输入：第1个矩阵的行数和第1个矩阵到第6个矩阵的列数，以一个空格分隔。
输出：矩阵连乘A1,...,An的最少数乘次数为15125，最优计算次序为((A1(A2A3))((A4A5)A6))。
【数据规模】
矩阵个数在10以内。*/
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n){int r,i,j,k;for(i=0;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)//r个矩阵连乘{for(i=1;i<=n-r+1;i++){//r个矩阵的r-1个空隙中依次测试最优点j=i+r-1;m[i][j]=m[i][i]+m[i+1][j]+A[i-1]*A[i]*A[j];s[i][j]=i;for(k=i+1;k<j;k++)//变换分隔位置，逐一测试{int t=m[i][k]+m[k+1][j]+A[i-1]*A[k]*A[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}
}
void print(int i,int j){if(i==j){cout<<"A"<<i;return;}cout<<"(";print(i,s[i][j]);print(s[i][j]+1,j);//递归1到s[i][j]cout<<")";
}
int main(void){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n=0;while(scanf("%d",&A[n++])!=EOF){;}n-=2;MatrixChain(n);cout<<m[1][n]<<endl;print(1,n);return 0;
}

/*【问题描述】
使用动态规划算法解最长公共子序列问题，具体来说就是，依据其递归式自底向上的方式依次计算得到每个子问题的最优值。
【输入形式】
在屏幕上输入两个序列X和Y。
【输出形式】
序列Xi和Yj的最长公共子序列的长度。这个输出的最长公共子序列选取的方法是：当xi!=yj时，而c[i-1,j]==c[i,j-1],那么，c[i,j]是由c[i-1,j]得到的。其中c[i,j]中存放的是：序列Xi和序列Yj的最长公共子序列的长度。
当最长公共子序列为空时，输出最长公共子序列长度为0，最长公共子序列为：None。
【样例1输入】
ABCBDAB
BDCABA
【样例1输出】
4
BCBA
【样例1说明】
输入：第一行输入序列X的各元素，第二行输入序列Y的各元素。
输出：序列X和Y的最长公共子序列的长度为4，其中一个最长公共子序列为：BCBA。
【样例2输入】
ABCD
EFGH
【样例2输出】
0
None
【样例2说明】
输入：第一行输入序列X的各元素，第二行输入序列Y的各元素。
输出：序列X和Y的最长公共子序列为空，最长公共子序列的长度为0，最长公共子序列为：None。
【数据规模】序列长度不超过20。*/
#include<bits/stdc++.h>
using namespace std;
string x,y;
//0左上方，1左，2上
vector<vector<int>> c(30,vector<int>(31));
vector<vector<int>> b(30,vector<int>(31));
vector<vector<int>>lcs_length(){int m=x.size();int n=y.size();for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=0;}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]=1;}}}return c;
}
void print(int str1_len,int str2_len){if(str1_len==0||str2_len==0){return;}if(b[str1_len][str2_len]==0){print(str1_len-1,str2_len-1);cout<<x[str1_len-1];}else if(b[str1_len][str2_len]==2){print(str1_len-1,str2_len);}else{print(str1_len,str2_len-1);}
}
int main(void){cin>>x>>y;auto c=lcs_length();cout<<c[x.size()][y.size()]<<'\n';if(c[x.size()][y.size()]==0)cout<<"None";elseprint(x.size(),y.size());return 0;
}

/*【问题描述】
使用动态规划算法解最大子段和问题，具体来说就是，依据递归式，按照顺序求得子问题。
【输入形式】
在屏幕上输入一个序列元素，包含负整数、0和正整数。
【输出形式】
序列的最大子段和，及得到最大子段和时的起始和终止编号。可能会存在多个最优解, 样例输出的是起始编号最小的那个最优解, 并且最优解包含的元素最少.
【样例1输入】
-2 1 -1 6 -4 5 -5 -2 0 7
【样例1输出】
7
4
6
【样例1说明】
输入：10个数，元素间以空格分隔。
输出：序列的最大子段和7，得到最大子段和时的起始编号为4，终止编号为6。虽然最后一个元素7也是一个最优解，但是起始编号更大，因此不是所求的最优解。
【样例2输入】
1 -1 6
【样例2输出】
6
3
3
【样例2说明】
输入：3个数，元素间以空格分隔。
输出：序列的最大子段和6，得到最大子段和时的起始编号为3，终止编号为3。虽然{1, -1, 6}三个数加起来为6，但是包含了3个元素，而{6}只包含了1个元素，因此{6}是所求的最优解。
【样例3输入】
0 8
【样例3输出】
8
2
2
【样例3说明】
输入：2个数，元素间以空格分隔。
输出：序列的最大子段和8，得到最大子段和时的起始编号为2，终止编号为2。虽然{0, 8}二个数加起来为8，但是包含了2个元素，而{8}只包含了1个元素，因此{8}是所求的最优解。
【数据规模】
序列的长度不超过100。*/
#include<bits/stdc++.h>
using namespace std;
int a[150],n;
struct node{int sum;int l,r;
}; 
int main(){while(scanf("%d",&a[n])!=EOF){n++;}n--;if(n==0){cout<<0<<'\n'<<0<<'\n'<<0;return 0;}node ans,temp;ans=temp={INT_MIN,-1,-1};for(int i=0;i<=n;++i){if(temp.sum>0){temp.sum+=a[i];temp.r=i;}else{temp.sum=a[i];temp.l=temp.r=i;}if(temp.sum>ans.sum){ans=temp;}}cout<<ans.sum<<'\n';cout<<ans.l+1<<'\n';cout<<ans.r+1<<'\n';return 0;
}

/*【问题描述】
使用分治递归算法解最大子段和问题，具体来说就是，将序列分为长度相等的左右两段，分别求出这两段的最大子段和，包含左右部分子段的最大子段和，求这三种情况得到的最大子段和的最大值。
【输入形式】
在屏幕上输入一个序列元素，包含负整数、0和正整数。
【输出形式】
序列的最大子段和，及得到最大子段和时的起始和终止编号。可能会存在多个最优解, 样例输出的是起始编号最小的那个最优解, 并且最优解包含的元素最少.
【样例1输入】
-2 1 -1 6 -4 5 -5 -2 0 7
【样例1输出】
7
4
6
【样例1说明】
输入：10个数，元素间以空格分隔。
输出：序列的最大子段和7，得到最大子段和时的起始编号为4，终止编号为6。虽然最后一个元素7也是一个最优解，但是起始编号更大，因此不是所求的最优解。
【样例2输入】
1 -1 6
【样例2输出】
6
3
3
【样例2说明】
输入：3个数，元素间以空格分隔。
输出：序列的最大子段和6，得到最大子段和时的起始编号为3，终止编号为3。虽然{1, -1, 6}三个数加起来为6，但是包含了3个元素，而{6}只包含了1个元素，因此{6}是所求的最优解。
【样例3输入】
0 8
【样例3输出】
8
2
2
【样例3说明】
输入：2个数，元素间以空格分隔。
输出：序列的最大子段和8，得到最大子段和时的起始编号为2，终止编号为2。虽然{0, 8}二个数加起来为8，但是包含了2个元素，而{8}只包含了1个元素，因此{8}是所求的最优解。
【数据规模】序列的长度不超过100。*/
#include<bits/stdc++.h>
using namespace std;
int a[150],n;
struct node{int sum;int l,r;
}; 
node betterNode(const node& a,const node& b){//比较原则：（不重叠）大小>起始编号>元素个数；（重叠）大小>元素个数>起始编号if(a.r<b.l||b.r<a.l){//比较原则：（不重叠）大小>起始编号>元素个数if(a.sum>b.sum) return a;if(a.sum<b.sum) return b;if(a.l<b.l) return a;if(a.l>b.l) return b;if(a.r-a.l<b.r-b.l) return a;if(a.r-a.l>b.r-b.l) return b;return a;//a=b}else{//比较原则:（重叠）大小>元素个数>起始编号if(a.sum>b.sum) return a;if(a.sum<b.sum) return b;if(a.r-a.l<b.r-b.l) return a;if(a.r-a.l>b.r-b.l) return b;return a.l<b.l?a:b;}
}
node MaxSubSum(int left,int right){node ans;ans.sum=0;if(left==right) {ans.sum=a[left];//ans.sum=a[left]>0?a[left]:0;ans.l=left;ans.r=right;}else{int center=(left+right)/2;node leftans=MaxSubSum(left,center);node rightans=MaxSubSum(center+1,right);int lefts=0;node s1;s1.sum=INT_MIN;s1.r=center;for(int i=center;i>=left;i--){lefts+=a[i];if(lefts>s1.sum){s1.sum=lefts;s1.l=i;}}int rights=0;node s2;s2.sum=INT_MIN;s2.l=center+1;for(int i=center+1;i<=right;i++){rights+=a[i];if(rights>s2.sum){s2.sum=rights;s2.r=i;}}ans.sum=s1.sum+s2.sum;ans.l=s1.l;ans.r=s2.r;ans=betterNode(ans,leftans);ans=betterNode(ans,rightans);}return ans;
}
int main(){while(scanf("%d",&a[n])!=EOF){n++;}n--;if(n==0){cout<<0<<'\n'<<0<<'\n'<<0;return 0;}node ans=MaxSubSum(0,n);cout<<ans.sum<<'\n';cout<<ans.l+1<<'\n';cout<<ans.r+1<<'\n';return 0;
}

/*【问题描述】
使用动态规划算法解凸多边形最优三角剖分问题，具体来说就是，依据递归式，按照顺序求得子问题，使得该三角剖分中诸三角形上权之和为最小。
【输入形式】
在屏幕上输入凸多边形顶点个数和顶点坐标。按逆时针顺序输入顶点坐标。
【输出形式】
最优三角剖分后的三角形顶点。
【样例输入】
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26
【样例输出】
012
234
024
456
046
【样例说明】
输入：顶点个数为7，每一行为一个顶点坐标，以空格分隔。如下图所示，第二行至第八行分别为顶点v0~v6的坐标。
输出：每一行为顺序产生的最优三角剖分后的三角形顶点。
【数据规模】
顶点个数不超过10。*/
#include<bits/stdc++.h>
using namespace std;
//t：i-1到j的凸多边形最优权值，w:i到j的权值，s:与vi-1和vj一起构成三角形的第3个顶点的位置
int t[100][100],w[100][100],s[100][100],n,inf=99999;
struct node{int x,y;
}p[100];
int W(int i,int k,int j){//三角形i,k,jreturn w[i][k]+w[k][j]+w[i][j];
}
void MIN_WEIGHT(){for(int i=1;i<n;i++)t[i][i]=0;for(int len=2;len<=n;len++){for(int i=1;i<=n-len+1;i++){int j=i+len-1;t[i][j]=inf;for(int k=i;k<j;k++){int q=t[i][k]+t[k+1][j]+W(i-1,k,j);if(q<t[i][j]){t[i][j]=q;s[i][j]=k;}}}}return;
}
void print(int i,int j){if(i==j) return;print(i,s[i][j]);print(s[i][j]+1,j);cout<<i-1<<s[i][j]<<j<<'\n';return;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){cin>>p[i].x>>p[i].y;w[i][i]=0;}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){int disx=p[j].x-p[i].x;int disy=p[j].y-p[i].y;w[i][j]=sqrt(disx*disx+disy*disy);}}//顶点i到j的距离MIN_WEIGHT();print(1,n-1);return 0;
}

/*【问题描述】
使用动态规划算法解0-1背包问题，具体来说就是，依据递归式，按照顺序求得子问题，使得选择合适物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
【输入形式】
在屏幕上输入背包容量、物品数量、每件物品价值和重量。
【输出形式】
最优解时所选物品的价值总和及其编号。
【样例输入】
10
5
6 3 5 4 6
2 2 6 5 4
【样例输出】
15
1 2 5
【样例说明】
输入：背包容量10、物品数量5、每件物品价值6, 3, 5, 4, 6和重量2, 2, 6, 5, 4。
输出：最优解时选择物品的价值总和为15，编号为1,2,5。
提示：按照教材的代码求解最优解。也就是, 当m[i+1,j]和m[i+1,j-wi]+vi相同时，不选当前物品i，x[i]为0。
【数据规模】物品个数不超过10。*/
#include<bits/stdc++.h>
using namespace std;
//v:价值,w:质量,x:是否选,m[i][j]:剩 i 个物品 放入容量为 j 的背包的最大价值
int c,n,v[1000],w[1000],m[1000][1000],x[1000];
void Knapsack(){int jmax=min(w[n]-1,c);for(int j=0;j<=jmax;j++)m[n][j]=0;for(int j=w[n];j<=c;j++)m[n][j]=v[n];for(int i=n-1;i>=1;i--){jmax=min(w[i]-1,c);for(int j=0;j<=jmax;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]);}
}
void Traceback(){int cc=c;for(int i=1;i<n;i++){if(m[i][cc]==m[i+1][cc])x[i]=0;else{x[i]=1;cc-=w[i];}}x[n]=m[n][cc]?1:0;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>c>>n;for(int i=1;i<=n;i++){cin>>v[i];}for(int i=1;i<=n;i++){cin>>w[i];}Knapsack();Traceback();cout<<m[1][c]<<'\n';for(int i=1;i<=n;i++)if(x[i]==1)cout<<i<<" ";return 0;
}

第四章——贪心算法 

/*【问题描述】
Dijkstra算法解决的是带权重的有向图上单源最短路径问题。所有边的权重都为非负值。设置顶点集合S并不断地作贪心选择来扩充这个集合。使用最小堆数据结构构造优先队列。第1个顶点为源。
【输入形式】
在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
【输出形式】
顺序给出从源到各个顶点的最短距离及路径。
【样例输入】
5
0 10 0 30 100
0 0 50 0 0
0 0 0 0 10
0 0 20 0 60
0 0 0 0 0
【样例输出】
10: 1->2
50: 1->4->3
30: 1->4
60: 1->4->3->5
【样例说明】
输入：顶点个数为5。连接顶点间边的权矩阵大小为5行5列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：每行给出源1到其余各顶点（顺序给出）的最短距离及路径，冒号后有一空格。如果源1到该顶点没有路，则输出："inf: 1->u"，其中u为该顶点编号。
【数据规模】
顶点的个数不超过10。*/
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,g[15][15],pre[15],vis[15],dis[15];
struct edge{int u,v,w;bool operator<(const edge &a) const{return w>a.w;//如果当前边的权值 w 大于另一条边的权值 a.w，那么当前边的优先级更低。这样优先队列会将权值最小的边放在堆顶。}
};
priority_queue<edge> q;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>g[i][j];if(g[i][j]==0){g[i][j]=INF;}}for(int i=1;i<=n;i++){if(i!=1){pre[i]=1;dis[i]=g[1][i];q.push({1,i,dis[i]});}}int cnt=1,temp=1;//当前边数while(!q.empty()){edge t=q.top();q.pop();if(vis[t.v]) continue;vis[t.v]=1;cnt++;if(cnt==n) break;temp=t.v;//判断从1经过temp到i的距离是否更短for(int i=2;i<=n;i++){if(!vis[i]&&dis[temp]+g[temp][i]<dis[i]){dis[i]=dis[temp]+g[temp][i];pre[i]=temp;q.push({temp,i,dis[i]});}}}for(int i=2;i<=n;i++){if(dis[i]==INF){cout<<"inf: 1->"<<i<<'\n';continue;}stack<int> s;int t=i;while(t!=0){s.push(t);t=pre[t];}cout<<dis[i]<<": "<<s.top();s.pop();while(!s.empty()){cout<<"->"<<s.top();s.pop();}cout<<'\n';}return 0;
}

/*【问题描述】
使用贪心算法求解Huffman编码问题，具体来说就是，根据每个字符的出现频率，使用最小堆构造最小优先队列，构造出字符的最优二进制表示，即前缀码。
【输入形式】
在屏幕上输入字符个数和每个字符的频率。
【输出形式】
每个字符的Huffman编码。字符从a开始，依次为b, c, ...
【样例输入】
6
45 13 12 16 9 5
【样例输出】
a 0
b 101
c 100
d 111
e 1101
f 1100
【样例说明】
输入：字符个数为6，a至f每个字符的频率分别为：45, 13, 12, 16, 9, 5。
输出：a至f每个字符对应的Huffman编码。
说明：为了保证每个字符对应的Huffman编码的唯一性，对于所有测试样例，得到的Huffman编码树中，对于任何一个除叶结点以外的结点，其左儿子结点的频率小于其右儿子结点的频率（两者不会相等）。
【数据规模】
字符个数小于或等于10。*/
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,l;
struct node{int f=0,l=-1,r=-1,i=-1;bool operator<(node a) const{return f>a.f;}
}a[105];
string b[15];
priority_queue<node> q;
void BackTrace(int h,string s){if(a[h].i<n){b[h]=s;return;}BackTrace(a[h].l,s+'0');BackTrace(a[h].r,s+'1');
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){cin>>a[i].f;a[i].i=i;q.push(a[i]);}l=n;while(q.size()!=1){node n1=q.top();q.pop();node n2=q.top();q.pop();a[++l].f=n1.f+n2.f;a[l].i=l;a[l].l=n1.i;a[l].r=n2.i;q.push(a[l]);}int head=q.top().i;BackTrace(head,"");for(int i=0;i<n;i++){char c=i+'a';cout<<c<<" "<<b[i]<<'\n';}return 0;
}

/*最小生成树 prime（贪心算法）
【问题描述】
Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。Q使用最小堆数据结构。
【输入形式】
在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
【输出形式】
顺序输出按照贪心选择得到的各顶点序号，及该顶点的前驱顶点序号，及路径长度。
【样例1输入】
8
0 15 7 0 0 0 0 10
15 0 0 0 0 0 0 0
7 0 0 9 12 5 0 0 
0 0 9 0 0 0 0 0
0 0 12 0 0 6 0 0
0 0 5 0 6 0 14 8
0 0 0 0 0 14 0 3
10 0 0 0 0 8 3 0
【样例1输出】
3 1 7
6 3 5
5 6 6
8 6 8
7 8 3
4 3 9
2 1 15
【样例说明】
输入：顶点个数为8。连接顶点间边的权矩阵大小为8行8列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：顺序输出按照贪心选择得到的各顶点序号，及该顶点的前驱顶点序号，及路径长度。*/
#include<bits/stdc++.h>
using namespace std;
int n,g[15][15],vis[15];
const int INF=0x3f3f3f3f;
struct node{int u,v,w;bool operator<(const node &a)const{return w>a.w;}
};
priority_queue<node> q;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>g[i][j];if(g[i][j]==0)g[i][j]=INF;}}int temp=1,cnt=0;for(int i=2;i<=n;i++){if(g[temp][i]!=INF){q.push({temp,i,g[temp][i]});}}vis[1]=1;cnt++;while(!q.empty()){node t=q.top();q.pop();if(vis[t.v]) continue;vis[t.v]=1;cnt++;cout<<t.v<<' '<<t.u<<' '<<t.w<<'\n';if(cnt==n) break;temp=t.v;for(int i=1;i<=n;i++){if(!vis[i]&&g[temp][i]!=INF){q.push({temp,i,g[temp][i]});}}}return 0;
}