1

我有一套硬币 1,2,4,10,20,40,100,200,400,1000,2000 美分。我想知道有多少种方式可以支付一定金额（<= 6000）。我目前在 c++ 中的解决方案是使用动态编程，如下所示：

long long d[6010];
int coin[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
d[0] = 1;
for (int i = 0; i < 11; i++) {  // iterate through all coins
    for (int j = 1; j <= 6000; j++)
        d[j] += d[j - coin[i]];
printf("%lld\n", d[20]);

但是我的输出不正确：-956301262。是因为任何溢出问题吗？

4

3 回答 3

2

您必须使用大小为 6001x11 的二维数组（在您的情况下）来存储所有可能的值。从 d[0][0] 开始并迭代直到 d[6000][10] 包含最终答案。

于 2013-03-06T09:16:39.520 回答
1

你的循环是向后的。硬币面额循环应该是你的内循环。

您的数组分配也没有任何意义。您目前只是将与您的目标不同的特定硬币面额的变化值相加。

您可能应该将向量向量作为数据结构。每次运行内部循环时，都应该在数据结构中插入一个新向量。这个向量应该是一组硬币，其总和等于感兴趣的价值。

于 2013-03-06T07:41:49.543 回答
1

我看不出你的算法应该如何工作，我会从高到低递归地遍历每个面额（循环不同的数量）。在使用查找表时，大概类似于您的 d.

类似于以下内容：

howmanyways(sorted_denominations_set_starting_with_1, target amount):
if this is already in the lookup table return the result
else if sorted_denominations_set_starting_with_1 is {1}, then return target amount
else loop over 0 to target amount/last_set_element
   return the sum of results for howmanyways(sorted_denominations_set_starting_with_1 without the largest element, target amount-last_set_element*loop_index)
keep whatever you return in the lookup table

并返回 howmanyways({1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}, 目标金额);

于 2013-03-06T07:10:17.453 回答