最大化不能收集相邻行和列的硬币的价值

PHPz

发布时间：2023-09-12 22:13:02

1500人浏览过

来源于tutorialspoint

转载

最大化不能收集相邻行和列的硬币的价值

动态规划是一种优化算法技术，通过将特定问题分解为一些简单的子问题来解决它们。通过这个过程，我们可以将完整搜索的质量、条件或事实结合起来，以获得精确且准确的贪心算法。但这种方法本身就是一个矛盾，因为它有很大的优点，但这也是它最大的缺点和限制。我们可以将一个问题划分为一些子问题，但我们不能再划分子问题。它们应该可以自行解决。子问题的概念可以用来解决更重要的问题，因为它们本质上是高度优化的。

什么是硬币以及如何兑换它？

硬币是表示总金额整数和的数组的组成部分。在这个过程中，您应该返回一些硬币来平衡总和。如果没有构建，则返回-1。

更换硬币有两种解决方案 -

递归 - 单纯且慢的方法。
动态规划 - 一种及时高效的方法

计算机科学中硬币的应用 -

用于分发更改。

硬币操作的算法

以下是我们如何逐步提高相邻行中硬币价值的过程。

第一步 - 开始
第二步 - 构建一个长度为 n+1 的新数组
第 3 步 - 将动态 prog[0] 设置为 1 以进行单向处理
步骤 4 - 迭代该值
第5步 - 将dynamicprog[index-coins[i]]的值添加到dynamicprog[index]

Transor
专业的AI翻译工具，支持网页、字幕、PDF、图片实时翻译

下载
步骤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
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 
using namespace std;
int findMax(vector& arr) {
   int n = arr.size(), result = 0;
   vector 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 >& matrix){
   int m = matrix.size();
   if (m == 0)
      return 0;
   vector dp;
   for (int i = 0; i < m; i++) {
      int val = findMax(matrix[i]);
   dp.push_back(val);
   }
   return findMax(dp);
}
int main() {
   vector > arr = { { 2, 7, 6, 5 },
      { 9, 9, 1, 2 },
      { 3, 8, 1, 5 } };
   int result = solve(arr);
   cout << result;
   return 0;
}