டைனமிக் புரோகிராமிங்-சி ++ செயல்படுத்தலின் நாணய சேகரிப்பு சிக்கல்

Coin Collection Problem Dynamic Programming C Implementation

நாணய சேகரிப்பு சிக்கல் பின்வருமாறு விவரிக்கப்பட்டுள்ளது: சில நாணயங்களை என்எக்ஸ்எம் கட்டம் பலகையில் வைக்கவும், மேல் இடதுபுறத்தில் உள்ள ரோபோ முடிந்தவரை பல நாணயங்களை கீழ் வலதுபுறத்தில் சேகரிக்க வேண்டும், ரோபோ வலது அல்லது கீழ் நோக்கி நகர முடியும். ரோபோ சேகரிக்கக்கூடிய அதிகபட்ச நாணயங்களை கணக்கிட்டு, அதன் பாதையை கண்டுபிடிக்கவா?

வழிமுறைகளின் பகுப்பாய்வு:
ரோபோ (i, j) க்கு நகரும்போது சேகரிக்கப்பட்ட அதிகபட்ச நாணயங்களின் எண்ணிக்கையாக F (i, j) இருக்கட்டும்.
F (i, j) = அதிகபட்சம் {F (i-1, j), F (i, j-1)} + cij, 1<=i<=n,1<=j<=m
// நீங்கள் மேலே இருந்து நகரவில்லை, அல்லது இடமிருந்து தற்போதைய நிலைக்கு நகரவில்லை என்றால், பெரிய மதிப்பை எடுத்துக் கொள்ளுங்கள்!
எஃப் (0, ஜே) = 0, 1<=j<=m F(i,0)=0, 1<=i<=n,
// சதுரங்கப் பலகைக்கு வெளியே 0 வது வரிசை மற்றும் 0 வது நெடுவரிசையை அமைத்து பூஜ்ஜியத்திற்குத் திரும்புக.
(I, j) கட்டத்தில் நாணயங்கள் இருந்தால், சிஜ் 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) } } }

செயல்பாட்டு விளைவு பின்வருமாறு:
பிங்கோ! இந்த சிக்கல் தீர்க்கப்படுகிறது.