首页 文章

动态编程中的核心转储错误

提问于
浏览 次
0

我正在修改一个程序，确定给定数量的更改所需的硬币数量最少 . 这个硬币系统只有三个硬币：0.01美元，0.06美元，0.10美元 . 因此，对于13美分，如果硬币是3，则最小数量为3.对于56美分，最小数量为6，等等 . 程序执行该部分，我的部分是回溯跟踪备忘录表以确定每个使用的硬币的数量 . 因此，例如，13美分，最低为3硬币，这些硬币为2 6美分硬币和1美分硬币 .

下面生成的备忘录表格如下所示：

1cent  0 1 2 3 4 5 6 7 8 9 10 11 12 13
6cent  0 1 - 3 - - - 2 - -  -  -  -  3
10cent 0 - - 3 - - - - - -  -  -  -  3

对于这样的事情，我们总是从右下角开始 . 我试图递归地做这件事 . 我注意到了一种模式 . 如果我们有一个数字，并且它上面的数字不是相同的数字，那么我们"jump"在同一行 cent 空格的左边 . 所以在底行， 10 cent 行，最后我们看到从13跳到3，这是10个空格 . 如果一个数字和上面的数字是相同的数字，这意味着硬币在那么多次之后停止使用，我们向上移动一行 . 所以在上表中我们从右下角开始， 3 . 上面的数字也是一个 3 ，所以由于已经有0 "jumps"，所使用的10美分硬币的数量是0，我们向上移动到下一行，即 6 cent 行 .

现在我们比较 3 和 13 . 这两个数字不相等所以我们移过 6 空格 . 因此，截至目前我们已经 1 "jump" . 现在我们来看看 2 和 7 . 这两个也不相等所以我们移动了 6 个空格，现在我们有 2 "jumps" . 现在我们比较 1 和 1 并且它们是相等的，所以我们向上移动一行并从那一点开始 . 由于我们在过去的行中有 2 "jumps"，因此使用的 6 cent 币数为 2 . 对于最后一部分，它会让人感到困惑 . 当我们向上移动时，我们从我们所在的同一列开始 . 由于我们正在比较 1 和 1 ，我们将从该列继续 . 由于这是行 0 的最后一行，因此剩下的更改量始终是顶部的数字 . 在我的示例中，我们向上移动了一行并从 1 开始，因此使用的 1 cent 硬币数量为 1 . 这意味着使用的硬币总数是：

1 cent: 1
 6 cent: 2
10 cent: 0

我知道这是措辞非常混乱 . 希望我的代码能够更好地展示这一点 . 以下是我尝试实现此操作的方法：

void countCoins( uint i, uint a, uint coinVal,
                 const vector< uint > & denom,
                 Matrix< uint > & memo )
{
   uint numCoins = 0;

   // Check the current value with the value above it
   if( memo.at(i, a) != memo.at(i - 1, a) )
   {
      if( denom.at(i) == coinVal )
      {
         numCoins++;
      }

      countCoins( i, a - denom.at(i), coinVal, denom, memo );    // If not equal, "jump" over
   }
   else
   {
      if( i > 0 )
      {
         countCoins( i - 1, a, coinVal, denom, memo );    // If equal, move up a row
      }
      else
      {
         numCoins += a;    // If equal and the row number is 0
      }
   }
}

这段代码编译，但是当我运行它时，我收到一条消息，上面写着“matrix.h：48：Object＆Matrix :: at（uint，uint）[with Object = unsigned int; uint = unsigned int]：断言`row < rows && col <cols'失败 . 中止（核心转储）“我不明白为什么 . 有谁知道为什么我会收到这个核心转储消息？

c++ dynamic-programming memoization

1 回答

  • 0

    在尝试访问 memo 和/或 denom 之前，需要检查 i 和 a 是否小于 0 .

    void countCoins( uint i, uint a, uint coinVal,
                 const vector< uint > & denom,
                 Matrix< uint > & memo )
{
    if (i < 0) {
        // handle edge case and return
    }

    if (a < 0) {
        // handle edge case and return
    }

    uint numCoins = 0;

    ...
    ...

}

    注意：如果 i 和 a 的值大于 memo 和 denom 的大小，则还需要检查 . 但是在你的代码中，似乎你总是递减它们，所以可能不是这样 .

    回复于

相关问题