硬币找零，但只有硬币

enter image description here

的算法，我想出了是一样的东西：

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，如果：我们总是可以用1枚硬币面额的我来解决 amt = i。对于第一种情况，如果：如果我们有没有使用当前面额的的解决方案，我们可以重复使用该解决方案。对于第二否则如果：如果当前的面额都可以使用（< = AMT），以及面额不使用，我们可以...

对于复杂：表是大小呐。每个单元需要O（1）次填充。有人能帮助我指出正确的方向吗？

来源

2013-05-01 Jiew Meng

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

在正确性方面，我会说，解释重现关系和基本情况会很好。作为一个风格点，我不会浏览代码并证明每一行的正确性，而是专注于大局。因此，请解释您的表格代表什么以及如何设置基本案例和重现关系，读者可以轻松查看代码并查看您是否实现了该功能。

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

来源

2013-05-07 18:14:45 alexcole

硬币找零，但只有硬币

回答

相关问题