實驗三 動態規劃實驗
- 第1關：編程實作矩陣連乘問題的求解
- 第2關：編程實作最大子段和問題的求解（分別采用分治法和動態規劃法求解）
- 第3關：0-1背包
- 第4關：最長單調子序列
- 第5關：最長公共子序列（LCS）
第1關：編程實作矩陣連乘問題的求解
題目描述：
在計算矩陣連乘積時，加括號的方式對計算量有影響，
例如： 有三個矩陣A1，A2，A3連乘，它們的維數分別為
10100,1005,550，用第一種加括號方式（A1A2）A3計算，則所需數乘次數為101005+10550=7500，用第二種加括號方式A1（A2A3）計算，需要100550+10100*50=75000次數乘，
輸入連乘矩陣的個數，每個矩陣的維數，要求輸出最少數乘次數，
相關知識
輸入格式
第一行輸入一個n，代表有n個矩陣
接下來n行，每行輸入兩個數a,b，代表每個矩陣的維度，
0<n,a,b<100
輸出格式
輸出一個數，代表最小數乘次數，
測驗輸入:
6
30 35
35 15
15 5
5 10
10 20
20 25
預期輸出：
15125
代碼：
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int a[n][2];
int b[n][n]={0};
for(int i=0;i<n;i++){
scanf("%d %d",&a[i][0],&a[i][1]);
}
for(int i=1;i<n;i++){
for(int j=0;j<n-i;j++){
b[j][j+i]=b[j][j]+b[j+1][j+i]+a[j][0]*a[j][1]*a[j+i][1];
int k=j+1;
for(;k<j+i;k++){
int t=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1];
if(t<b[j][j+i]) {
b[j][j+i]=t;
}
//也可以直接三元運算子：b[j][j+i]=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1]<b[j][j+i]?b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1]:b[j][j+i];
}
}
}
printf("%d",b[0][n-1]);
return 0;
}
第2關：編程實作最大子段和問題的求解（分別采用分治法和動態規劃法求解）
題目描述：
對于給定序列a1,a2,a3……an,尋找它的某個連續子段，使得其和最大，如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和為20，
輸入格式
第一行輸入一個n，代表有n個數
下面一行輸入n個數，代表序列
0<n<100
序列中的數的范圍為[-2000,2000]
輸出格式
輸出一個數，代表最大欄位和，
測驗輸入:
6
-2 11 -4 13 -5 -2
預期輸出：
20
代碼：
第一種：分治法
#include<stdio.h>
int Largestsubsection(int a[],int m,int n){
if(n==m){
return a[n];
}
int cent=(m+n)/2;
int d=Largestsubsection(a,m,cent)>Largestsubsection(a,cent+1,n)?Largestsubsection(a,m,cent):Largestsubsection(a,cent+1,n);
int left=0,s1=0;
for(int i=cent;i>=m;i--){
left+=a[i];
if(left>s1){
s1=left;
}
}
int right=0,s2=0;
for(int i=cent+1;i<=n;i++){
right+=a[i];
if(right>s2){
s2=right;
}
}
int sum=s1+s2;
return d>sum?d:sum;
}
int main(){
int n;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
printf("%d",Largestsubsection(a,0,n-1));
return 0;
}
第二種：動態規劃法
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int a[n][2];
int max=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i][0]);
if(i==0){
a[i][1]=a[i][0];
}
else{
a[i][1]=a[i-1][1]+a[i][0]>a[i][0]?a[i-1][1]+a[i][0]:a[i][0];
}
max=max>a[i][1]?max:a[i][1];
}
printf("%d",max);
return 0;
}
第3關：0-1背包
題目描述：
給定n個物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為c，問應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大？
相關知識
動態規劃
輸入格式
第一行輸入一個n，c，代表有n個物品背包容量為c
接下來n行，每行輸入wi，和vi
其中0<n,c,wi,vi<5000
輸出格式
輸出一個數，代表最大價值
測驗輸入:
4 8
2 3
3 4
4 5
5 6
預期輸出：
10
代碼：
#include<stdio.h>
int main(){
int n,c;
scanf("%d %d",&n,&c);
int a[n][2],b[n][c+1]={0};//一個存題目資料，一個構建最優解，
for(int i=0;i<n;i++){
scanf("%d %d",&a[i][0],&a[i][1]);
for(int j=1;j<c+1;j++){
if(i==0){
if(a[i][0]>j){
b[i][j]=0;
}
else{
b[i][j]=a[i][1];
}
}
else{
if(a[i][0]<=j){
b[i][j]=b[i-1][j]>a[i][1]+b[i-1][j-a[i][0]]?b[i-1][j]:a[i][1]+b[i-1][j-a[i][0]];
}
else{
b[i][j]=b[i-1][j];
}
}
}
}
printf("%d",b[n-1][c]);
return 0;
}
第4關：最長單調子序列
題目描述
給定一個序列，求這個序列的最長上升子序列的長度，并輸出這個最長上升子序列，題目保證，最長上升子序列只有一個，
相關知識
最長上升子序列
輸入格式
第一行輸入一個n，代表序列長度
第二行輸入n個值，代表這個序列
0<n<1000
-1000<序列內的數<1000
輸出格式
第一行輸出一個數，代表最長上升子序列的長度，
第二行列印這個子序列，
測驗輸入：
8
5 2 8 6 3 6 5 7
輸出
4
2 3 6 7
代碼：
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int m[n][3];
m[0][1]=1;
m[0][2]=0;
for(int i=0;i<n;i++){
scanf("%d",&m[i][0]);
if(i!=0){
int k=i-1;
while(k>=0){
if(m[i][0]>m[k][0]){
m[i][1]=m[k][1]+1;
m[i][2]=k;
break;
}
k--;
}
if(k<0){
m[i][1]=1;
m[i][2]=i;
}
}
}
int max=m[0][1],j=0;
for(int i=0;i<n;i++){
if(m[i][1]>=max){
max=m[i][1];
j=i;
}
}
printf("%d\n",max);
int a[max],c=max;
while(m[j][2]!=j){
max--;
a[max]=m[j][0];
j=m[j][2];
}
a[max-1]=m[j][0];
for(int i=0;i<c;i++){
printf("%d ",a[i]);
}
return 0;
}
第5關：最長公共子序列（LCS）
題目描述
給定兩個序列X=ABCBDAB, Y=BDCABA，求X和Y的最長公共子序列
相關知識
動態規劃
輸入格式
兩行，每行為一個長度不超過500的字串（全為大寫字串）
輸出格式
輸出一個數，最長公共子序列的長度，若不存在公共子序列，則輸出0，
測驗輸入
ABCBDAB
BDCABA
測驗輸出
4
代碼：
方法一：
（自己想的）
#include<stdio.h>
#include<string.h>
int main(){
char x[500]={'\0'},y[500]={'\0'};
scanf("%s",x);
scanf("%s",y);
int m=strlen(x),n=strlen(y);
int a[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(x[i]==y[j]){
a[i][j]=1;
}
else{
a[i][j]=0;
}
}
}
int max=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][j]==1){
int t=1,k=i+1,l=j+1;
while(k<m&l<n){
int g=l;//記錄l
while(l<n&&a[k][l]==0){
l++;
}
if(a[k][l]==1){ t++;l++;}
else{
l=g; //即本排沒有1
}
k++;
}
max=max>t?max:t;
}
}
}
printf("%d",max);
return 0;
}
方法二：
(演算法課上講的DP方法）
#include<stdio.h>
#include<string.h>
int main(){
char x[500]={'\0'},y[500]={'\0'};
scanf("%s",x);
scanf("%s",y);
int m=strlen(x),n=strlen(y);
int a[m+1][n+1]={0};
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(x[i]==y[j]){
a[i][j]=a[i-1][j-1]+1;
}
else{
a[i][j]=a[i][j-1]>a[i-1][j]?a[i][j-1]:a[i-1][j];
}
}
}
printf("%d",a[m][n]);
return 0;
}
注：答案不唯一，僅供參考，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279303.html
標籤：其他