检测整数是否可以写为给定整数的总和

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文档中查找了相应的函数.