動态規劃之經典例題

1、三角數塔問題

設有一個三角形的數塔，頂點為根結點，每個結點有一個整數值。從頂點出發，可以向左走或向右走，如圖所示：

要求從根結點開始，請找出一條路徑，使路徑之和最大，隻要輸出路徑的和。

【代碼】

//

// 例題1 三角數字塔問題 //

#include <stdio.h>

#include <stdlib.h>

#define MAXN 101

int n,d[MAXN][MAXN];

int a[MAXN][MAXN];

void fnRecursive(int,int);

//遞推方法函數聲明

int fnMemorySearch(int,int);

//記憶化搜尋函數聲明

int main()

{

int i,j;

printf("輸入三角形的行數n(n=1-100):\n");

scanf("%d",&n);

printf("按行輸入數字三角形上的數(1-100):\n");

for(i=1; i<=n; i++)

for(j=1; j<=i; j++)

scanf("%d",&a[i][j]);

d[i][j]=-1;//初始化名額數組

printf("遞推方法：1\n記憶化搜尋方法：2\n");

int select;

scanf("%d",&select);

if(select==1)

fnRecursive(i,j);//調用遞推方法

printf("\n%d\n",d[1][1]);

}

if(select==2)

printf("\n%d\n",fnMemorySearch(1,1));//調用記憶化搜尋方法

else

printf("輸入錯誤！");

return 0;

void fnRecursive(int i,int j)

//遞推方法實作過程

for(j=1; j<=n; j++)

d[n][j]=a[n][j];

for(i=n-1; i>=1; i--)

d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);

int fnMemorySearch(int i,int j)

//記憶化搜尋實作過程

if(d[i][j]>=0) return d[i][j];

if(i==n) return(d[i][j]=a[i][j]);

if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1))

return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));

return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));

2、硬币問題

問題描述：有n種硬币，面值分别為V1,V2,…,Vn, 每種有無限多。給定非負整數S，可以選用多少硬币，使得面值之和恰好為S，輸出硬币數目的最小值和最大值。（1<=n<=100,0<=S<=10000,1<=Vi<=S）

// 例題1 硬币問題 //

#define INF 100000000

#define MAXNUM 10000

#define MONEYKIND 100

int n,S;

int V[MONEYKIND];

int min[MAXNUM],max[MAXNUM];

void dp(int*,int*);

void print_ans(int*,int);

//輸出函數聲明

int i;

printf("輸入硬币的種數n(1-100):\n");

printf("輸入要組合的錢數S(0-10000):\n");

scanf("%d",&S);

printf("輸入硬币種類：\n");

scanf("%d",&V[i]);

dp(min,max);

printf("最小組合方案：\n");

print_ans(min,S);

printf("\n");

printf("最大組合方案：\n");

print_ans(max,S);

void dp(int *min,int *max)

//遞推過程實作

min[0] = max[0] = 0;

for(i=1; i<=S; i++)//初始化數組

min[i]=INF;

max[i]=-INF;

for(i=1; i<=S; i++)

if(i>=V[j])

if(min[i-V[j]]+1<min[i]){

min[i]=min[i-V[j]]+1;//最小組合過程

//printf("%d\n",min[i]);

if(max[i-V[j]]+1>max[i])

max[i]=max[i-V[j]]+1;//最大組合過程

void print_ans(int *d,int S)

//輸出函數實作

if(S>=V[i]&&d[S]==d[S-V[i]]+1)

printf("%d-",V[i]);

print_ans(d,S-V[i]);

break;

3、矩形嵌套問題

問題描述：有n個矩形，每個矩形可以用兩個整數a,b描述，表示它的長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中，當且僅當a<c,b<d或者b<c,a<d（相當于把矩形X旋轉90度）。例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)内。你的任務是選出盡量多的矩形排成一行，使得除了最後一個之外，每一個矩形都可以嵌套在下一個矩形内。

// 例題2 矩形嵌套問題 //

#define MAXNUM 100//矩形的最大個數

struct Rect

int x;

int y;

};

int n;//矩形個數

struct Rect rect[MAXNUM];

int G[MAXNUM][MAXNUM];//鄰接有向圖

int d[MAXNUM];//過程數組

int dp(int i,int G[MAXNUM][MAXNUM]);

int i,j,z;

printf("輸入矩形個數n(1-100):\n");

printf("輸入矩形的長和寬：\n");

scanf("%d",&rect[i].x);

scanf("%d",&rect[i].y);

if(rect[i].x<rect[j].x&&rect[i].y<rect[j].y)

G[i][j]=1;

printf("輸入要開始的矩形z：\n");

scanf("%d",&z);

//printf("%d-",z);

int temp = dp(z,G);

printf("最大可嵌套個數：%d\n",temp);

int dp(int i,int G[MAXNUM][MAXNUM])

int j;

if(d[i]>0)

return d[i];

d[i]=1;

if(G[i][j])

if(dp(j,G)+1>d[i])

d[i]=dp(j,G)+1;

4、求一組數列的最長的不下降序列。

問題描述：設有一個正整數序列b1，b2，b3，……，bn，若下标為i1<i2<i3，……<ik且有bi1≤bi2≤……bik則稱存在一個長度為k的不下降序列。可能有多個不下降序列，輸出最長序列的長度。

樣例輸入：13　7　9　16　38　24　37　18

　樣例輸出：5 (7 9 16 24 37)

// 例題2 數組的最長不下降序列問題 //

#define MAXNUM 100//最大數字個數

int b[MAXNUM][2];

int n;

int len;

printf("輸入數列中數字的個數n(1-100)：\n");

printf("輸入數字：\n");

scanf("%d",&b[i][0]);

b[i][1]=1;

for(i=2; i<=n; i++)

len = 0;

for(j=1; j<i; j++)

if((b[i][0]>=b[j][0])&&(b[j][1]>len))

len=b[j][1];

if(len>0)

b[i][1]=len+1;

len = 1;

for(j=2; j<=n; j++)

if(b[j][1]>len)

len = b[j][1];

printf("最長為：%d\n",len);

5、0-1背包問題

給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

// 0-1背包問題 //

#define MAXN 100//物品種類最大數量

int w[MAXN],V[MAXN];

int C;//最大容量

int n;//物品種類

int d[MAXN][MAXN];

int jMax;

int min(int,int);

//兩數之間的最小值

int max(int,int);

//兩數之間的最大值

void print_ans(int d[][MAXN],int,int);

//構造最優解并輸出

printf("輸入物品種類數n(1-100):\n");

printf("輸入每個種類的重量：\n");

scanf("%d",&w[i]);

printf("輸入每個種類的價值：\n");

printf("輸入背包的容量C：\n");

scanf("%d",&C);

jMax=min(C,w[n]-1);

for(j=0; j<=jMax; j++)