-1

问题是：

在此处输入图像描述

我想出的算法是这样的：

pair<bool, bitmask>[n][A] memo;     
// memo[i][j].first will be true if its possible to 
// use up to i-th denomination for amt j
// memo[i][j].second will contain info on which 
// denominations are used
for i = 0 to n:
    for j = 1 to A:
    if (i==j): C[i][j] = {true, {i}}
    else if (C[i-1][j].first == true): C[i][j] = C[i-1][j]]
    else if (...see recurrance relation...): 
        C[i][j] = {true, C[i-1][j]+{denom[i]}}
    else: C[i][j] = false

到目前为止是否正确？但我不确定如何证明它的正确性......我的尝试看起来只是用英文重写代码......

对于第一个如果：我们总是可以使用 1 个面额 i 的硬币来解决 amt=i。对于第一个 else if：如果我们有一个不使用当前面额的 amt 解决方案，我们可以重用该解决方案。对于第二个 else if：如果可以使用当前面额（<= amt），并且不使用面额，我们可以...

对于复杂性：表的大小为 nA。每个单元格需要 O(1) 时间来填充。有人可以帮我指出正确的方向吗？

4

1 回答 1

0

是的，我会说你在这里完全走在正确的轨道上。您要解决的问题本质上是子集和问题，您的解决方案是标准动态编程问题（请参阅http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution）。

就正确性而言，我会说解释递归关系和基本情况就可以了。作为文体观点，我不会仔细阅读代码并证明每一行的合理性，而是专注于大局。因此，只需解释您的表格代表什么以及如何设置基本案例和重复关系，读者就可以轻松地查看代码并看到您实现了它。

对于运行时：是的，您的算法只是循环遍历表格的元素并填写它们，因此您的解释是正确的。

于 2013-05-07T18:14:45.857 回答