具体来说,问题是:
给定面值数组coins[]
, 每个硬币的限制数组limits[]
和数量amount
, 返回minimum需要的硬币数量,以获得amount
,或者如果不可能返回 null。另外填充数组change
解决方案中使用的每个硬币的数量。
这是我的解决方案:
public static int? Dynamic(int amount, int[] coins, int[] limits, out int[] change)
{
int[] minCoins = new int[amount + 1];
int[,] coinsUsedToAmount = new int[coins.Length, amount + 1];
minCoins[0] = 1;
for (int j = 0; j < amount; ++j)
{
if (minCoins[j] == 0)
{
continue;
}
for (int i = 0; i < coins.Length; ++i)
{
if (coinsUsedToAmount[i, j] >= limits[i])
{
continue;
}
int currAmount = j + coins[i];
if (currAmount <= amount
&& (minCoins[currAmount] == 0
|| minCoins[currAmount] > minCoins[j] + 1))
{
minCoins[currAmount] = minCoins[j] + 1;
for (int k = 0; k < coins.Length; ++k)
{
coinsUsedToAmount[k, currAmount] = coinsUsedToAmount[k, j];
}
coinsUsedToAmount[i, currAmount] += 1;
}
}
}
if (minCoins[amount] == 0)
{
change = null;
return null;
}
change = new int[coins.Length];
for(int i = 0; i < coins.Length; ++i)
{
change[i] = coinsUsedToAmount[i, amount];
}
return minCoins[amount] - 1;
}
但一般情况下是行不通的。
我的问题是例如在这种情况下:
amount = 141,
coins = new int[] { 2, 137, 65, 35, 30, 9, 123, 81, 71 }
limits = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1 }
最优解是:
change = new int[] { 1, 0, 1, 1, 1, 1, 0, 0, 0 }
我的算法给出null
作为结果。换句话说,它失败了,每当在某种程度上,我就不得不使用比可能的情况更不理想的解决方案,然后,最后,我没有必要的硬币。
因此,在这个例子中,我的算法在以下步骤中犯了错误:
minCoins[132] = (9 + 123) // 2 coins
但应该是:
minCoins[132] = (2 + 65 + 35 + 30) // 4 coins
因为这样我就可以使用9并有141.
几周以来我一直在思考这个问题,但仍然无法解决。我在这个网站和其他网站上看到了许多类似问题的解决方案,但没有一个对我有帮助。