0

请原谅我的天真，因为我没有太多的编程经验。在谷歌搜索一个不相关的问题时，我偶然发现了这个：

https://www.geeksforgeeks.org/find-number-of-solutions-of-a-linear-equation-of-n-variables/

我完全理解第一段（效率极低）的代码。但第二个：

def countSol(coeff, n, rhs): 

    # Create and initialize a table 
    # to store results of subproblems 
    dp = [0 for i in range(rhs + 1)] 
    dp[0] = 1

    # Fill table in bottom up manner 
    for i in range(n): 
        for j in range(coeff[i], rhs + 1): 
            dp[j] += dp[j - coeff[i]] 

    return dp[rhs]

让我困惑。我的问题是：为什么第二个程序要计算非负整数解的数量？

我写了几个例子，包括文章中给出的例子，我知道它确实做到了这一点。而且我了解它是如何填充列表的。但我不明白为什么会这样。

请原谅对某些人来说一定是一个无知的问题。但是我很想理解这个逻辑，因为我认为这样一个小片段非常聪明——它能够回答像“存在多少非负整数解”这样的一般问题（对于一些一般方程）。

4

1 回答 1

0

这种算法非常酷，展示了从不同角度寻找解决方案的能力。

举个例子：3x + 2y + z = 6，其中 LHS 是左侧，RHS 是右侧。

dp[k]k将通过用非负整数值替换 LHS 变量来跟踪获得 RHS 值的唯一方法的数量。

该i循环遍历 LHS 中的变量。该算法首先将所有变量设置为零。所以，唯一可能的k值是零，因此

k        0   1   2   3   4   5   6 
dp[k] =  1   0   0   0   0   0   0

对于i = 0，我们将更新dp以反映如果x是 1 或 2 会发生什么。我们不关心 x > 2 因为解决方案都是非负的，并且 3x 太大了。j循环负责更新dp并dp[k]递增，因为我们可以通过将系数的副本添加到dp[k - 3]RHS 值。结果是k3k-3

k        0   1   2   3   4   5   6 
dp[k] =  1   0   0   1   0   0   1

现在算法继续i = 1，更新dp以反映所有可能的 RHS 值，其中 x 为 0、1 或 2，y 为 0、1、2 或 3。这次j循环增加1 dp[k]，dp[k-2]因为我们可以k通过添加 1来获得 RHS 值将系数复制2到k-2，得到

k        0   1   2   3   4   5   6 
dp[k] =  1   0   1   1   1   1   2

最后，该算法包含 z = 1、2、3、4、5 或 6，导致

k        0   1   2   3   4   5   6 
dp[k] =  1   1   2   3   4   5   7

除了在伪多项式时间内计算答案外，还dp对每个 RHS <= 输入右侧的答案进行编码。

于 2020-03-27T01:18:06.303 回答