编辑:我之前用过 2,5 和 16。但他们只是例子。但现在我想泛化任何 3 个数字。
我有一个数字让我们说 N。这个数字只能通过 x1、x2 和 x3 的加法形成吗？我们可以任意次数和任意组合地使用这三个数字。
这个可以通过动态规划解决还是有其他简单的方法？
最佳答案
使用 Chicken McNugget Theorem如果你只有 2 个互质值。否则，跳到动态编程解决方案。
去掉多余的16后(因为是2的幂，所以用更多的2代替)，2和5 互质，所以不能写成 2a + 5b 的最大数是 2*5 - 2 - 5 = 3。任何高于此的都可以写。
对于 2 和 5 的特殊情况，解决方案的存在性也可以这样论证:显然偶数可以仅使用 2 来写。对于赔率:
2k+1 = (2k - 4) + 5
因此，一旦它们变得足够大，也可以通过使用两个和一个 5 来编写它们。
对于 3 个或更多数字，请参见示例 Frobenius Numbers和 Numerical semigroups .
动态编程
或者如果你想坚持经典，动态规划:
dp[i] = true if we can reach sum i
dp[0] = true, false for the rest
for i = 0 to query_sum:
dp[i] = dp[i] or dp[i - input1] or dp[i - input2] or dp[i - input3]
关于algorithm - 使用小于给定数字的组合形成给定数字 x，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28615914/