Advertisement
GerexD

dinamikus-kincses

Feb 25th, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. #include <iostream>
  2. /**
  3. 4. Adott egy nxm-es tábla, melynek minden mezője egy adott értékű kincset tartalmaz. A bal felső sarokból elindulva szeretnénk eljutni a jobb alsó sarokba úgy,
  4. hogy a lehető legtöbb kincset szedjük össze, tudva azt, hogy csak jobbra illetve le tudunk menni.
  5. Pl: n=4, m=4 és a bemeneti mátrix, amely a kincseket tartalmazza:
  6. 1 2 2 7 1 3 5 12
  7. 6 3 1 7 7 10 11 19
  8. 4 4 5 6 11 15 20 26
  9. 3 2 1 2 14 17 21 28
  10. */
  11. using namespace std;
  12. void visszakeres(int b[][50],int n, int m)
  13. {
  14. int o=1,s=1;
  15. cout<<s<<" "<<o<<endl;
  16. for(int i=1;i<=n+m-2;i++)
  17. {
  18. if(b[s+1][o]>b[s][o+1]){
  19. cout<<s+1<<" "<<o<<endl;
  20. s++;}
  21. else {cout<<s<<" "<<o+1<<endl;
  22. o++;}
  23. }
  24. }
  25. int main()
  26. {
  27. int a[50][50]= {0},b[50][50]= {0},n,m;
  28. cout<<"N ";
  29. cin>>n;
  30. cout<<"M ";
  31. cin>>m;
  32. for(int i=1; i<=n; i++)
  33. for(int j=1; j<=m; j++)
  34. cin>>a[i][j];
  35. for(int i=1; i<=n; i++)
  36. for(int j=1; j<=m; j++)
  37. {
  38. if(i==1 && j==1) b[i][j]=a[i][j];
  39. else if(i==1 && j!=1) b[i][j]=b[i][j-1]+a[i][j];
  40. else if(i!=1 && j==1) b[i][j]=b[i-1][j]+a[i][j];
  41. else if(b[i-1][j]>b[i][j-1])
  42. b[i][j]=b[i-1][j]+a[i][j];
  43. else b[i][j]=b[i][j-1]+a[i][j];
  44. }
  45. cout<<b[n][m];
  46. cout<<endl;
  47. for(int i=1;i<=n;i++){
  48. for(int j=1;j<=m;j++)
  49. cout<<b[i][j]<<" ";
  50. cout<<endl;}
  51. visszakeres(b,n,m);
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement