algorithm - 具有负硬币值(value)的硬币总和

Question

我设法编写了这段代码来找到最小硬币总和以获得准确的值(value)量。但我写这篇文章时考虑到了正硬币值(value)。

有人可以告诉我如何升级此代码以计算具有负硬币值(value)的最小硬币总和吗？ 提前致谢!

int main()
{
 int arr[] = {1, 2, 3};
 int m = sizeof(arr)/sizeof(arr[0]);
 int n = 4;
 printf(" %d ", count(arr, m, n));
 return 0;
}


int count( int S[], int m, int n )
{
 int i, j, x, y;

 int table[n+1][m];

 for (i=0; i<m; i++)
    table[0][i] = 1;
  // Fill rest of the table enteries in bottom up manner
  for (i = 1; i < n+1; i++)
  {
    for (j = 0; j < m; j++)
    {
        // Count of solutions including S[j]
        x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
        // Count of solutions excluding S[j]
        y = (j >= 1)? table[i][j-1]: 0;
        // total count
        table[i][j] = x + y;
    }
}
return table[n][m-1];
}

Answer 1

目前尚不清楚您是要使用每个硬币任意次数(通常是如何陈述问题)，还是只想使用每个硬币 0 次或 1 次(这是您的代码所暗示的) .

如果允许您使用每个硬币任意次数，那么概念上最简单的解决方案可能是在编号为 0 到 N 的节点上构建一个图，其中 N 是所有正硬币值的总和，然后连接节点 i如果 (j-i) 是您的硬币值之一，则 j 具有有向边，然后运行 ​​Dijkstra 算法，其中所有边的权重为 1，以找到从 0 到图中所有其他节点的最短路径，其中将包括您的目标值。您可以回溯以找到适合您的目标值的特定最优解。

如果您最多只能使用每个硬币一次，那么您可以不失一般性地假设给定目标值的最优解将首先使用所有正硬币，然后使用所有负硬币。因此，您可以使用广度优先搜索使用所有正硬币(其中 N 再次是所有正硬币值的总和)为值 0 到 N 建立最佳解决方案，您可以跟踪每个目标值需要多少硬币，以及最优解中使用的最后一个硬币，然后将正数硬币排序，然后一次拿一个硬币，考虑将每个硬币与当前可以获得的每个值相加，看看是否可以使用更少的数量获得新的值硬币。然后，在仅使用正硬币计算出所有最优解后，您可以对负值硬币进行排序，并以类似的方式反向处理最优解数组。