動態規劃實驗報告
時間:2020-09-26 16:18:04 來源:勤學考試網 本文已影響 人
華東師范大學計算機科學技術系上機實踐報告
內容與設計思想
1.對于以下5 個矩陣:
M1: 2?3, M2: 3?6, M3: 6?4, M4: 4?2, M5: 2?7 ,
找出這5個矩陣相乘需要的最小數量乘法的次數。
請給出一個括號化表達式,使在這種次序下達到乘法的次數最少。
輸入:
第一行為正整數N,表示有N組測試數據;
每組測試數據的第一行為n,表示有n個矩陣,2<=n<=50;
接下去的n行,每行有兩個整數x和y,表示第ni個矩陣是x*y的。
輸出:
對行每組數據,輸出一行,每行一個整數,最小的矩陣連乘積。
我們保證輸出的結果在2^64之內。
基本思想:
對于n個矩陣的連乘積,設其不同的計算次序為P(n)。
由于每種加括號方式都可以分解為兩個子矩陣的加括號問題:(A1...Ak)(Ak+1…An)可以得到關于P(n)的遞推式如下:
2.定義0/1/2背包問題為:。限制條件為:,且。設f(i , y)表示剩余容量為y,剩余物品為:i,i+1,…,n時的最優解的值。
1.)給出f(i , y)的遞推表達式;
2.)請設計求解f(i , y)的算法,并實現你的算法;
3.)設W=[10,20,15,30],P=[6,10,15,18],c=48,請用你的算法求解。
輸入:
第一行為一個正整數N,表示有幾組測試數據。
每組測試數據的第一行為兩個整數n和M,0<n<=20,0<M<100000。
再下去的n行每行有兩個整數Wi和Pi, 0<Wi,Pi<10000。
輸出:
對行每組數據,輸出一行,每行一個整數,最小的矩陣連乘積。
我們保證輸出的結果在2^64之內。
基本思想:
對第 i 個物品代價w ,價值v,
for(i=1;i<=n;i++)
for(j=m;j>=w[i];j--)
if(dp[j]<dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
3.設G為有n個頂點的有向無環圖,G中各頂點的編號為1到n,且當<i,j>為G中的一條邊時有i < j。設w(i,j)為邊<i,j>的長度,請設計動態規劃算法,計算圖G中最長路徑。并分析算法的時間復雜性。
輸入:
輸入一個數n(1<=n<=200),表示有n個點,接下來一個數m,表示有m條路,接下來m行中每行輸入2個數a ,b,v表示從a點到b點有條路,路的長度為v。
接下來輸入一個數p,表示有p次詢問,在接下來的p行中每行輸入2個數a,b,算出此圖中從a到b的最長路徑。
輸出:
對每個詢問p,(a,b),輸出從a到b之間的最長路.如果a,b之間沒連通,輸出-1。
基本思想:
Floyd算法。時間復雜度是O(n^3).
4. 【裝箱問題】:有一個箱子容量為V(正整數,0≤V≤20000),同時有 N個物品(0<N≤30),每個物品有一個體積(正整數)。要求從N個物品中,任取若干個裝入箱內,使箱子的剩余空間為最小。
輸入:
輸入有多組測試數據,第一行一個正整數V,表示箱子的容量
第二行一個數據n表示物品個數。
第三行有n個數據,描述每個物品的體積
輸出:
每個輸出占一行,輸出箱子最后剩下的最小體積
基本思想:
類似0-1背包問題,弄成0-1背包的反面,看0-1背包那些值可以達到,再用n減去離他最近的比他小的值即為所得。
5.【數字三角形】:給定一個具有N層的數學三角形,從頂至底有多條路徑,每一步可沿左斜線向下或沿右斜線向下,路徑所經過的數字之和為路徑得分,請求出最小路徑得分及相應路徑。
輸入:
輸入數據首先包括一個整數C,表示測試實例的個數,每個測試實例的第一行是一個整數N(1 <= N <= 100),表示數塔的高度,接下來用N行數字表示數塔,其中第i行有個i個整數,且所有的整數均在區間[0,99]內。
輸出:
對于每個測試實例,輸出可能得到的最小和。
并在下一行輸出路徑。
基本思想:
從上往下遍歷,每一層每一個數都記錄從1到它的最小值,最后從最后一層中找出最小數即可。
調試過程
附錄
1)完全加括號的矩陣連乘積
#include<stdio.h>
int p[51];
__int64 m[51][51];
int f(int n)
{
int i,j,k;
for(i=1;i<=n;i++)
m[i][i]=0;
for(k=1;k<n;k++)
for(i=1;i<=n-k;i++)
{
m[i][i+k]=m[i][i]+m[i+1][i+k]+p[i-1]*p[i]*p[i+k];
for(j=i+1;j<i+k;j++)
{
if(m[i][i+k]>m[i][j]+m[j+1][i+k]+p[i-1]*p[j]*p[i+k])
m[i][i+k]=m[i][j]+m[j+1][i+k]+p[i-1]*p[j]*p[i+k];
}
}
return 0;
}
int main()
{
int N,n,i;
scanf("%d",&N);
while(N--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&p[i],&p[i+1]);
f(n);
printf("%I64d\n",m[1][n]);
}
}
2)0-1背包問題
#include<stdio.h>
int w[25],v[25];
int dp[100001];
int main()
{
int n,m,N;
int i,j;
scanf("%d",&N);
while(N--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=m;i++)
dp[i]=0;
for(i=1;i<=n;i++)
for(j=m;j>=w[i];j--)
if(dp[j]<dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
printf("%d\n",dp[m]);
}
}
3)最長路
#include<stdio.h>
int x[201][201];
int main()
{
int i,j,k;
int n,m;
int a,b,v,p;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x[i][j]=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&v);
x[a][b]=v;
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
for(k=i+1;k<j;k++)
if(x[i][k]+x[k][j]>x[i][j])
x[i][j]=x[i][k]+x[k][j];
scanf("%d",&p);
while(p--)
{
scanf("%d%d",&a,&b);
if(x[a][b]==0)
printf("-1\n");
else printf("%d\n",x[a][b]);
}
}
}
4)裝箱問題
#include<stdio.h>
int w[31];
int dp[20001];
int main()
{
int n,N;
int i,j;
while(scanf("%d",&N)!=EOF)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=0;i<=N;i++)
dp[i]=0;
dp[0]=1;
for(i=1;i<=n;i++)
for(j=N;j>=0;j--)
if(dp[j]==1&&(j+w[i])<=N)
dp[j+w[i]]=1;
for(i=N;dp[i]==0;i--);
printf("%d\n",N-i);
}
}
5)數塔
#include<stdio.h>
int a[101][101];
int min[101][101];
int main()
{
int N,n,i,j,x;
scanf("%d",&N);
while(N--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
min[1][1]=a[1][1];
for(i=2;i<=n;i++)
for(j=1;j<=i;j++)
{
if(j==1)
min[i][j]=min[i-1][j]+a[i][j];
else if(j==i)
min[i][j]=min[i-1][j-1]+a[i][j];
else
{
if(min[i-1][j]>min[i-1][j-1])
min[i][j]=min[i-1][j-1]+a[i][j];
else min[i][j]=min[i-1][j]+a[i][j];
}
}
x=min[n][1];
for(i=2;i<=n;i++)
if(min[n][i]<x)
x=min[n][i];
printf("%d\n",x);
}
}