算法實驗報告

華北電力大學實驗報告||試驗名稱算法設計與分析課程名稱算法設計與分析||11試驗一矩陣連乘一、試驗目標熟悉動態(tài)規(guī)劃算法設計思想和設計步驟，掌握基本程序設計方法，培養(yǎng)學生用計算機處理實二、試驗要求：用動態(tài)規(guī)劃算法解矩陣連乘問題（1）問題描述給定n個矩陣{A1,A2,…,An}，其中Ai與Ai+1是可乘，i=1,2,…,n-1。要算出這n個矩陣連乘積A1A2…An。因為矩陣乘法滿足結合律，故計算矩陣連乘積能夠有許多不一樣計算次序。這種計算次序能夠用加括號方式來確定。若一個矩陣連乘積計算次序完全確定，也就是說該連乘積已完全加括號，則能夠依此次序重復調用2個矩陣相乘標準算法計算出矩陣連乘積。完全加括號矩陣連乘積可遞歸地定義為：（1）單個矩陣是完全加括號；（2）矩陣連乘積A是完全加括號，則A可表示為2個完全加括號矩陣連乘積B和C乘積并加括號，即A=(BC)。比如，矩陣連乘積A1A2A3A4有5種不一樣完全加括號方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一個完全加括號方式對應于一個矩陣連乘積計算次序，這決定著作乘積所需要計算量。若A是一個p×q矩陣，B是一個q×r矩陣，則計算其乘積C=AB標準算法中，需要進行pqr次數(shù)乘。為了說明在計算矩陣連乘積時，加括號方式對整個計算量影響，先考查3個矩陣{A1,A2,A3}連乘情況。設這三個矩陣維數(shù)分別為10×100，100×5，5×50。加括號方式只有兩種：（（A1A2）A3），（A1（A2A3）），第一個方式需要數(shù)乘次數(shù)為10×100×5＋10×5×50＝7500，第二種方式需要數(shù)乘次數(shù)為100×5×50＋10×100×50＝75000。第二種加括號方式計算量時第一個方式計算量10倍。由此可見，在計算矩陣連乘積時，加括號方式，即計算次序對計算量有很大影響。于是，自然提出矩陣連乘積最優(yōu)計算次序問題，即對于給定相繼n個矩陣{A1,A2,…,An}（其中矩陣Ai維數(shù)為pi-1×pi，i＝1,2,…,n），怎樣確定計算矩陣連乘積A1A2…An計算次序（完全加括號方式），使得依此次序計算矩陣連乘積需要數(shù)乘次數(shù)最少。窮舉搜索法計算量太大，它不是一個有效算法，本試驗采取動態(tài)規(guī)劃算法解矩陣連乘積最優(yōu)計算次序問題。（2）算法設計思想動態(tài)規(guī)劃算法基本思想是將待求解問題分成若干個子問題，先求解子問題，然后從這些子問題解得到原問題解。與分治法不一樣是，動態(tài)規(guī)劃法經(jīng)分解得到子問題往往不是相互獨立，前一子問題解為后一子問題解提供有用信息，能夠用一個表來統(tǒng)計全部已處理子問題答案，不論該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。本試驗算法思緒是：1、計算最優(yōu)值算法MatrixChain()：建立兩張表（即程序中**m和**s，利用二維指針存放），一張表存放矩陣相乘最小運算量，主對角線上值為0，依次求2個矩陣、3個矩陣…、直到n個矩陣相乘最小運算量，其中每次矩陣相乘最小運算量都在上一次矩陣相乘最小運算量基礎上求得，最終一次求得值即為n個矩陣相乘最小運算量；另一張表存放最優(yōu)斷開位置。2、輸出矩陣結合方式算法Traceback()：矩陣結合即是給矩陣加括號，打印出矩陣結合方式，由遞歸過程Traceback()完成。分三種情況：（1）只有一個矩陣，則只需打印出A1；（2）有兩個矩陣，則需打印出（A1A2）；（3）對于矩陣數(shù)目大于2，則應該調用遞歸過程Traceback()兩次，結構出最優(yōu)加括號方式。三、試驗儀器及設備visualstudio。程序設計#include"stdafx.h"#include<iostream>usingnamespacestd;constintMAX=100;//p用來統(tǒng)計矩陣行列，main函數(shù)中有說明//m[i][j]用來統(tǒng)計第i個矩陣至第j個矩陣最優(yōu)解//s[][]用來統(tǒng)計從哪里斷開才可得到該最優(yōu)解intp[MAX+1],m[MAX][MAX],s[MAX][MAX];intn;//矩陣個數(shù)intmatrixChain(){for(inti=0;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//對角線循環(huán)for(inti=0;i<=n-r;i++)//行循環(huán){ intj=r+i-1;//列控制//找m[i][j]最小值，先初始化一下，令k=im[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j+1];s[i][j]=i;//k從i+1到j-1循環(huán)找m[i][j]最小值for(intk=i+1;k<j;k++) {inttemp=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];if(temp<m[i][j]) {m[i][j]=temp;//s[][]用來統(tǒng)計在子序列i-j段中，在k位置處//斷開能得到最優(yōu)解s[i][j]=k; } }}returnm[0][n-1];}//依照s[][]統(tǒng)計各個子段最優(yōu)解，將其輸出voidtraceback(inti,intj){if(i==j){cout<<'A'<<i;return;}if(i<s[i][j])cout<<'(';traceback(i,s[i][j]);if(i<s[i][j])cout<<')';if(s[i][j]+1<j)cout<<'(';traceback(s[i][j]+1,j);if(s[i][j]+1<j)cout<<')';}voidtraceback(){cout<<'(';traceback(0,n-1);cout<<')';cout<<endl;}intmain(){cout<<"請輸入矩陣個數(shù)："<<endl;cin>>n;cout<<"輸入矩陣（形如a*b,中間用空格隔開）:"<<endl;for(inti=0;i<=n;i++)cin>>p[i];//測試數(shù)據(jù)能夠設為六個矩陣分別為//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]//則p[0-6]={30,35,15,5,10,20,25}cout<<"輸出結果以下："<<endl;matrixChain();traceback(0,n-1);//最終解值為m[0][n-1];cout<<endl;return0;}數(shù)據(jù)輸入和結果輸出六、試驗總結：此次試驗基本達成了試驗目標，用動態(tài)規(guī)劃思想處理了矩陣連乘問題。在這次試驗過程中，剛開時編程時候疑惑了很長時間，編程需要注意算法代碼與實際語言結合。在進行代碼驗證時不但需要驗證給定數(shù)據(jù)還要自編數(shù)據(jù)驗證。試驗二0-1背包（動態(tài)規(guī)劃）試驗目標：1.利用動態(tài)規(guī)劃思想，設計處理上述問題算法，找出最大背包價值裝法。2.掌握動態(tài)規(guī)劃應用二、試驗要求：問題描述:給定n種物品和一背包。物品i重量是wi，其價值為vi，背包容量為C。問應怎樣選擇裝入背包物品，使得裝入背包中物品總價值最大?在選擇裝入背包物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包數(shù)次，也不能只裝入部分物品。0-1背包問題是一個特殊整數(shù)規(guī)劃問題三、試驗儀器：visualstudio四、試驗代碼：題目分析：0-1背包問題具備最優(yōu)子結構性質，能夠據(jù)此定義遞歸關系，建立遞歸方程，并以自底向上方式計算最優(yōu)值，依照計算最優(yōu)值時得到信息，結構最優(yōu)解。#include"stdafx.h"#include"iostream";usingnamespacestd;intn=5;intw[]={0,3,2,1,4,5};intv[]={0,25,20,15,40,50};intx[5];intV[6][7];intC=6;voidmain(void){ inti,j; for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=C;j++) V[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=C;j++) { if(j<w[i]) V[i][j]=V[i-1][j]; else { if(V[i-1][j]>V[i-1][j-w[i]]+v[i]) V[i][j]=V[i-1][j]; else V[i][j]=V[i-1][j-w[i]]+v[i]; } } } //以上結構動態(tài)規(guī)劃表 j=C; for(i=n;i>0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } printf("動態(tài)規(guī)劃表以下：\n"); for(i=0;i<6;i++) { for(j=0;j<7;j++) { printf("%8d",V[i][j]); } printf("\n"); } printf("裝入背包物品：\n"); for(i=0;i<6;i++) printf("%4d",x[i]); printf("\n背包取得最大值：\n"); printf("%4d\n",V[n][C]);}五、試驗結果：六、試驗總結：這次試驗用到是動態(tài)規(guī)劃法，0/1背包問題用動態(tài)規(guī)劃法首先要結構動態(tài)規(guī)劃表，用三個for語句實現(xiàn)；依照動態(tài)規(guī)劃表每行最大值改變確定每個元素裝入是否，逐步確定出裝入背包物品，背包容量最大值也就是動態(tài)規(guī)劃表最右下角。在此次試驗中碰到了動態(tài)規(guī)劃表結構紊亂情況，經(jīng)核查是因數(shù)組初始位置0混同成1造成。試驗三0-1背包（回溯法）一、試驗目標用回溯法處理0-1背包問題學會回溯法實際應用二、試驗要求問題描述:給定n種物品和一背包。物品i重量是wi，其價值為vi，背包容量為C。問應怎樣選擇裝入背包物品，使得裝入背包中物品總價值最大?在選擇裝入背包物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包數(shù)次，也不能只裝入部分物品，用回溯法處理該問題三、試驗儀器visualstudio四、試驗代碼#include<iostream.h>//定義min、max函數(shù)intmin(inta,intb){ if(a>=b)returnb; elsereturna;}intmax(inta,intb){ if(a>=b)returna; elsereturnb;}voidKnapsack(intv[6],intw[6],intc,intn,intm[6][6])//{ intjmax=min(w[n]-1,c); for(intj=0;j<jmax;j++) m[n][j]=0; for(intp=w[n];p<=c;p++) m[n][p]=v[n]; for(inti=n-1;i>1;i--) { jmax=min(w[i]-1,c); for(intj=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(intt=w[i];t<=c;t++) m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}voidTraceback(intm[6][6],intw[6],intc,intn,intx[6]){ for(inti=1;i<n;i++) if(m[i][c]==m[i+1][c])x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c]!=0)?1:0;}voidmain(){ intn1=5; intc1=6; intw1[6]={0,3,2,1,4,5}; intv1[6]={0,25,20,15,40,50}; intt[6][6]; intx1[6]; intm=0; //cout<<"請輸