php - 检测整数是否可以写成给定整数的总和

Question

假设我有常量 3,5,6,9,10。我如何检测如何将输入的 $n 写为这些常量的总和且项数最少？

例子

$n=10, S=10
$n=18, S=9+9
$n=24, S=9+9+6
$n=27, S=9+9+9
$n=28, S=10+9+9

谢谢

Answer 1

这是另一个 Python 解决方案，但希望您可以轻松转换为 PHP(我会自己做，但我不是 PHP 专家 - 我相信您可以做得更好)。我尽量不使用任何高级的 Python 函数，以便非 Python 的读者更容易理解，但如果某些 Python 语法不清楚，请尽管提问。

allowed = [3, 5, 6, 9, 10]
n = 28

solutions = [ None ] * (n + 1)
solutions[0] = []

for i in range(n + 1):
    if solutions[i] is None: continue
    for a in allowed:
        if i + a > n: continue
        if solutions[i + a] is None or len(solutions[i]) + 1 < len(solutions[i + a]):
            solutions[i + a] = solutions[i] + [a]

print solutions[28]

它的工作原理是从 0 开始并逐渐增加到所需的数量，并为每个可能的总数保留迄今为止看到的最短解决方案的缓存。它的运行时间为 O(n * a)，其中 a 是不同允许值的数量。

顺便说一句，你对 n=28 的回答是错误的。它应该是 [9, 9, 10]。

更新:这是我对 PHP 解决方案的尝试:

<?php
$allowed = array(3, 5, 6, 9, 10);
$n = 28;

$solutions = array();
$solutions[0] = array();

foreach (range(0, $n) as $i) {
    if (is_null($solutions[$i])) continue;
    foreach ($allowed as $a) {
        if ($i + $a > $n) continue;
        if (is_null($solutions[$i + $a]) ||
            sizeof($solutions[$i]) + 1 < sizeof($solutions[$i + $a])) {
            $solutions[$i + $a] = array_merge($solutions[$i], array($a));
        }
    }
}

var_dump($solutions[$n]);
?>

它给出了正确的答案，但请注意，我不是专业的 PHP 编码人员 - 我只是在 PHP 文档中查找了等效函数。