c++ - 查找最大数量的硬币和选定的硬币

Question

我正在做硬币行问题。我遇到了一个小问题。

有一排 n 个硬币，其值为一些正整数 c1, c2, ...。 。 。 , cn，不一定不同。

目标是在不能拾取任何两个相邻硬币的限制下拾取最大金额。例如，在下面的示例中，一旦您拿起 10，您就无法再拿起 6 或左侧的 2。

示例:

enter the number of coins: 6
enter the value of all coins : 5 1 2 10 6 2 
The maximum amount of coin : 17
The selected coins to get maximum value : C1 , C4 , C6

我想获得精选硬币(例如 C1、C4、C6)。

这是我的功能代码我只能在这段代码中获得最大金额。

int getanswer(int array[],int len)
{
  int C[20];
  for (int j = 0; j < len; j++)
  {
        C[j + 1] = array[j];
  }

  int F[20];
  F[0] = 0;
  F[1] = C[1];

  for (int j = 2; j < len+1; j++)
  {
      F[j] = max(C[j] + F[j - 2], F[j - 1]);
      printf("temp :%d\n", C[j]);
  }

  return F[len];
}

如何使用我的代码获得精选硬币？

Answer 1

一个好的解决方案将涉及递归、回溯和内存(动态编程)。编写一个递归例程，尝试从左端开始的每个可用选项，然后在剩余列表上递归。您当前的算法对于其可见范围内的不平衡值存在盲点(超出 2 个元素)。

这里有一些伪代码可以帮助您开始。

int pickup(coin[])
{
    // base case: <= 2 coins left
    if size(coin) == 0           // return 0 for an empty list
        return 0
    if size(coin) <= 2           // if only 1 or 2 coins left, return the larger
        return max(coin)

    // Otherwise, experiment:
    //   pick *each* of the first two coins, solve the remaining problem,
    //   and compare results.
    pick1 = coin[0] + pickup(coin[2:])      // pick 1st coin; recur on rest of list
    pick2 = coin[1] + pickup(coin[3:])      // pick 2nd coin; recur on rest of list

    return max(pick1, pick2)

这就是总攻击。通过内存，您可以大大加快求解速度。此外，您还需要将其转换为您的首选实现语言并为其添加跟踪，以便获得所需的索引。如果您需要的只是按顺序返回硬币值，则可以简单地累积这些值的数组，并在每次返回时预先添加一个值。