Maximieren Sie den Wert von Münzen, die nicht in benachbarten Zeilen und Spalten eingesammelt werden können

Dynamische Programmierung ist eine Optimierungsalgorithmustechnik, die spezifische Probleme löst, indem sie sie in eine Reihe einfacher Unterprobleme zerlegt. Durch diesen Prozess können wir Qualitäten, Bedingungen oder Fakten aus einer vollständigen Suche kombinieren, um einen präzisen und genauen Greedy-Algorithmus zu erhalten. Doch dieser Ansatz selbst ist ein Widerspruch, denn er hat große Vorteile, ist aber auch sein größter Nachteil und seine größte Einschränkung. Wir können ein Problem in Unterprobleme unterteilen, aber wir können es nicht in Unterprobleme unterteilen. Sie sollten sich selbst lösen. Das Konzept der Teilprobleme kann zur Lösung wichtigerer Probleme verwendet werden, da sie von Natur aus stark optimierend sind.

Was ist eine Münze und wie kann man sie einlösen?

Münzen sind Komponenten eines Arrays, das die Summe ganzer Zahlen darstellt, die den Gesamtbetrag darstellen. Dabei sollten Sie einige Münzen zurückgeben, um den Gesamtbetrag auszugleichen. Wenn nicht erstellt, wird -1 zurückgegeben.

Es gibt zwei Lösungen zum Wechseln von Münzen -

• Rekursion – einfache und langsame Methode.

• Dynamische Programmierung – eine zeitgemäße und effiziente Methode

Anwendungen von Münzen in der Informatik -

• Zum Verteilen von Änderungen.

Algorithmus der Münzoperation

Hier erfahren Sie, wie wir den Wert der Münzen in benachbarten Reihen schrittweise erhöhen.

• Schritt 1 – Starten

• Schritt 2 – Konstruieren Sie ein neues Array der Länge n+1

• Schritt 3 – Setzen Sie Dynamic Prog[0] auf 1 für die unidirektionale Verarbeitung

• Schritt 4 – Iterieren Sie den Wert

• Schritt 5 – Addieren Sie den Wert von „dynamicprog[index-coins[i]]“ zu „dynamicprog[index]

“.

• Schritt 6 – Legen Sie einen Bereich von 1 bis n fest

• Schritt 7 – Geben Sie einen Wert zurück

• Schritt 8 – Kündigung

Syntax von Münzen

If the coin value is greater than the dynamicprogSum, the coin is ignored, i.e.
dynamicprogTable[i][j]=dynamicprogTable[i-1][j].
If the coin value is less than the dynamicprogSum, you can consider it, i.e.
dynamicprogTable[i][j]=dynamicprogTable[i-
1].[dynamicprogSum]+dynamicprogTable[i][j-coins[i-1]].
Or;
maxCoins(i, j, d): Maximum number of coins that can be
collected if we begin at cell (i, j) and direction d.
   d can be either 0 (left) or 1 (right)
If (arr[i][j] == ‘#’ or isValid(i, j) == false)
   return 0
If (arr[i][j] == ‘C’)
   result = 1;
Else
   result = 0;
If (d == 0)
return result + max(maxCoins(i+1, j, 1),
   maxCoins(i, j-1, 0));
If (d == 1)
return result + max(maxCoins(i+1, j, 1),
   maxCoins(i, j+1, 0));

Hier ist die mögliche Münzwechselsyntax in einer C++-Umgebung. Durch die Anwendung dieser Syntax werden wir Code erstellen, um ein umfassendes Verständnis dieser Münze zu erlangen.

Zu befolgende Methode:

• Methode 1 – Rekursives C++-Programm zur Ermittlung der maximalen Anzahl an Münzen

• Methode 2: Maximieren Sie den Wert von Münzen, wenn Münzen in benachbarten Zeilen und Spalten nicht eingesammelt werden können.

Rekursives C++-Programm zum Ermitteln der maximalen Anzahl an Münzen

In diesem Code wenden wir dynamische Programmierung an. Die Logik ist: arr[i][j + 1] und arr[i][j – 1].

Die chinesische Übersetzung von

Beispiel 1

lautet:

Beispiel 1

#include<bits/stdc++.h>
using namespace std;
#define R 5
#define C 5
bool isValid(int i, int j) {
   return (i >=0 && i < R && j >=0 && j < C);
}
int maxCoinsRec(char arr[R][C], int i, int j, int dir){
   if (isValid(i,j) == false || arr[i][j] == '#')
      return 0;
   int result = (arr[i][j] == 'C')? 1: 0;
   if (dir == 1)
      return result + max(maxCoinsRec(arr, i+1, j, 0),
   maxCoinsRec(arr, i, j+1, 1));
   return result + max(maxCoinsRec(arr, i+1, j, 1),
   maxCoinsRec(arr, i, j-1, 0));
}
int main() {
   char arr[R][C] = {
      {'E', 'C', 'C', 'C', 'C'},
      {'C', '#', 'C', '#', 'E'},
      {'#', 'C', 'C', '#', 'C'},
      {'C', 'E', 'E', 'C', 'E'},
      {'C', 'E', '#', 'C', 'E'}
   };
   cout << "Maximum number of collected coins is "<< maxCoinsRec(arr, 0, 0, 1);
   return 0;
}

Ausgabe

Maximum number of collected coins is 8

Münzwert maximieren, wenn Münzen in benachbarten Zeilen und Spalten nicht eingesammelt werden können

In diesem C++-Code wenden wir die Methode an, die meisten Münzen zu finden und zu sammeln, bevor wir in eine Sackgasse geraten.

• Bewegen Sie sich einen Schritt vorwärts, d. h. Zelle (i, j+1), die Richtung bleibt unverändert.

• Gehen Sie einen Schritt nach unten und schauen Sie nach links, d. h. in die Zelle (i+1, j), und die Richtung ändert sich nach links.

Beispiel 2

wird übersetzt als:

Beispiel 2

#include <bits/stdc++.h>
using namespace std;
int findMax(vector<int>& arr) {
   int n = arr.size(), result = 0;
   vector<int> dp(n);
   dp[0] = arr[0];
   result = dp[0];
   if (n <= 1)
      return result;
   dp[1] = max(arr[1], arr[0]);
   result = max(result, dp[1]);
   for (int i = 2; i < n; i++) {
      dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]);
      result = max(result, dp[i]);
   }
   return result;
}
int solve(vector<vector<int> >& matrix){
   int m = matrix.size();
   if (m == 0)
      return 0;
   vector<int> dp;
   for (int i = 0; i < m; i++) {
      int val = findMax(matrix[i]);
   dp.push_back(val);
   }
   return findMax(dp);
}
int main() {
   vector<vector<int> > arr = { { 2, 7, 6, 5 },
      { 9, 9, 1, 2 },
      { 3, 8, 1, 5 } };
   int result = solve(arr);
   cout << result;
   return 0;
}

Ausgabe

25

Fazit

Heute haben wir in diesem Artikel gelernt, wie wir den Wert von Münzen aus Spalten maximieren können, die nicht aus benachbarten Zeilen gesammelt werden können, indem wir Code und Algorithmen in möglichst C++ erstellen.

Das obige ist der detaillierte Inhalt vonMaximieren Sie den Wert von Münzen, die nicht in benachbarten Zeilen und Spalten eingesammelt werden können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!