動的計画法のコイン収集問題-C ++実装



Coin Collection Problem Dynamic Programming C Implementation



コイン収集の問題は次のように説明されます。nxmグリッドボードにいくつかのコインを置きます。左上のロボットは右下にできるだけ多くのコインを収集する必要があります。ロボットは右または下に移動できます。ロボットが収集できるコインの最大数を計算し、その軌道を見つけますか?

アルゴリズムの分析:
ロボットが(i、j)に移動したときに収集されるコインの最大数をF(i、j)とします。
F(i、j)= max {F(i-1、j)、F(i、j-1)} + cij、1<=i<=n,1<=j<=m
//上から移動しない場合、または左から現在の位置に移動しない場合は、大きい方の値を使用してください。
F(0、j)= 0、1<=j<=m F(i,0)=0, 1<=i<=n,
//チェス盤の外側の0行目と0列目を設定し、ゼロに戻します。
(i、j)グリッドにコインがある場合、cijは1です。それ以外の場合は、0です。



分析例は次のとおりです。
画像
コインの最大数を計算するためのキーコード:

void FindMax() { for(int i=1i<=mi++) { for(int j=1j<=nj++) { F[i][j]=Max(F[i-1][j],F[i][j-1])+arr[i][j] } } printf(' Collect up to %d coins. ',F[m][n]) }

完全なコード実装:



#include #define MAX 10 int m,n //The rows and columns of the grid int arr[MAX][MAX] //Store the original grid elements int F[MAX][MAX] //Save the maximum number of coins collected int H[MAX][MAX]//When performing a backtracking operation, save the route coordinates void HuiSu() //Function declaration void FindMax() int Max(int a,int b) int main() { printf('Please enter the number of rows and columns of the grid: (separated by spaces) ') //The subscript 0 of the array in the rows and columns is not used scanf('%d%d',&m,&n) for(int i=0i<=mi++) //Set all 0 in column 0 {arr[i][0]=0} for(int j=0j<=nj++)//Set all 0 in row 0 {arr[0][j]=0} for(int i=1i<=mi++) { printf('Please enter the number of %d in line %d: (only 0 or 1 can appear) ',i,n) for(int j=1j<=nj++) { scanf('%d',&arr[i][j]) } } printf('The boards created in %d row %d column are as follows: ',m,n) for(int i=1i<=mi++) { for(int j=1j<=nj++) { printf('%d ',arr[i][j]) } printf(' ') } FindMax() printf('The route collected is: ') HuiSu() return 0 } int Max(int a,int b) //Find the larger value function { return a>=b? a:b } void FindMax() { for(int i=1i<=mi++) { for(int j=1j<=nj++) { F[i][j]=Max(F[i-1][j],F[i][j-1])+arr[i][j] } } printf(' Collect up to %d coins. ',F[m][n]) } void HuiSu()//Backtrack, find the current position, whether it came from the left or above. { int a=m int b=n H[1][1]=1 //The starting point and the ending point are the points that must be passed H[m][n]=1 // while(a>=1&&b>=1) { if(F[a-1][b]>=F[a][b-1]) { H[a-1][b]=1 a-- //The abscissa minus one, which means that it comes from the left } else { H[a][b-1]=1 b-- //The ordinate is subtracted by one, indicating that it came from the top } } for(int i=1i<=mi++) for(int j=1j<=nj++) { if(H[i][j]==1) { if(i==m&&j==n) printf('(%d,%d) ',m,n) else printf('(%d,%d)-->',i,j) } } }

操作効果は以下のとおりです。
ビンゴ!この問題は解決されました。