最大化不能收集相鄰行和列的硬幣的價值

動態規劃是一種最佳化演算法技術，透過將特定問題分解為一些簡單的子問題來解決它們。透過這個過程，我們可以將完整搜尋的品質、條件或事實結合起來，以獲得精確且準確的貪心演算法。但這種方法本身就是一個矛盾，因為它有很大的優點，但這也是它最大的缺點和限制。我們可以將一個問題分成一些子問題，但我們不能再劃分子問題。它們應該可以自行解決。子問題的概念可以用來解決更重要的問題，因為它們本質上是高度最佳化的。

什麼是硬幣以及如何兌換它？

硬幣是表示總金額整數和的陣列的組成部分。在這個過程中，您應該返回一些硬幣來平衡總和。如果沒有構建，則返回-1。

更換硬幣有兩種解決方案 -

• 遞歸 - 單純且慢的方法。

• 動態規劃 - 一個及時且有效率的方法

電腦科學中硬幣的應用 -

• 用於分發變更。

硬幣操作的演算法

以下是我們如何逐步提高相鄰行中硬幣價值的流程。

• 第一步 - 開始

• #第二步 - 建立一個長度為 n 1 的新陣列

• 第 3 步 - 將動態 prog[0] 設為 1 以進行單向處理

• 步驟 4 - 迭代該值

• 第5步 - 將dynamicprog[index-coins[i]]的值加到dynamicprog[index]

• 步驟6 - 設定一個從1到n的範圍

• #步驟7 − 傳回一個值

• 第 8 步 - 終止

硬幣的語法

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));

這裡是在C 環境中可能的硬幣找零語法。透過應用這個語法，我們將建立一些程式碼來全面了解這個硬幣。

遵循的方法：

• 方法 1 - 遞歸 C 程式找出最大硬幣數量

• 方法2−當無法收集相鄰行和列的硬幣時，最大化硬幣的價值

遞歸的C 程序，用於找到最大數量的硬幣

在這段程式碼中，我們應用了動態規劃。邏輯是：arr[i][j 1] 和 arr[i][j – 1]。

Example 1

的中文翻譯為：

範例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;
}

輸出

Maximum number of collected coins is 8

當相鄰行和列的硬幣無法收集時，使硬幣價值最大化

在這段 C 程式碼中，我們應用了在陷入死胡同之前查找並收集最多硬幣的方法。

• 向前移動一步，即單元格 (i, j 1)，方向保持不變。

• 向下移動一步並面向左邊，即單元格 (i 1, j) 且方向變為左。

Example 2

的翻譯為：

範例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;
}

輸出

25

結論

今天在這篇文章中，我們學習瞭如何透過可能的C 建立程式碼和演算法來最大化從相鄰行中不能收集的列的硬幣的價值。

以上是最大化不能收集相鄰行和列的硬幣的價值的詳細內容。更多資訊請關注PHP中文網其他相關文章！