检测整数是否可以表示为给定整数的和

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

谢谢

- user223083

---

目前您对解决方案有何想法？您卡在哪里了？ - Eric J.

这个问题是否应该被标记为作业？ - Mercurybullet

我考虑从最大到最小反复除以数，如果最终余数为0，则可以将其写成堆栈上数字的总和。然而，这不是一个好方法，以$n=17$为例。它会说$17=10+6$，余数为1。正确的解决方案应该是$S=6+6+5$。 - user223083

不，这不是一份作业。我只是把我的问题过于简单化了，以至于看起来像是一个作业 :)实际上，这是为了一个通过短信进行在线支付的系统。 - user223083

那么对于不能由这些常量之和表示的输入值呢？0、1、2、4、7、11……？ - Eric J.

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

- Mark Byers

---

好的，我会努力理解并最终接受你的解决方案。 - user223083

Skeetch：我试着将它转换为PHP。请查看我的更新答案。 - Mark Byers

这是一个不错的简短算法。我重新发布了一个清理过的 PHP 实现，更符合 PHP 的习惯用法。 - Josh Davis

Answer 2

这是Mark Byers的算法，使用更熟悉于PHP开发者的循环结构和不会产生PHP提示的构造进行了重写。 $C 是您的整数集合，$S 是解决方案。

$n = 28;
$C = array(3, 5, 6, 9, 10);
$S = array(array());

// if your set isn't sorted already, you have to call sort()
//sort($C);

for ($i = 0; $i <= $n; ++$i)
{
    if (!isset($S[$i]))
    {
        continue;
    }

    foreach ($C as $v)
    {
        if ($i + $v > $n)
        {
            break;
        }

        if (!isset($S[$i + $v])
         || count($S[$i + $v]) > 1 + count($S[$i]))
        {
            $S[$i + $v]   = $S[$i];
            $S[$i + $v][] = $v;
        }
    }
}

print_r($S[$n]);

- Josh Davis

---

当然。顺便说一下，如果你按升序对整数集进行排序，你可以提前退出内部循环，而不是遍历每个可能的组合。我已经相应地更新了上面的代码片段。 - Josh Davis

Answer 3

一个不可扩展但正确的解决方案草图（抱歉，目前只有Python..）：

#!/usr/bin/env python
import itertools, sys

pool = [3, 5, 6, 9, 10]

repeat, found, solutions = 1, False, set()

try: x = int(sys.argv[1])
except: x = 42

while not found:    
    for n in itertools.product(pool, repeat=repeat):
        s = sum(n)
        if s == x:
            solutions.add(n)
            found = True
            break
    repeat = repeat + 1

print solutions

将产生：

$ python 1850629.py 11
set([(5, 6)])

$ python 1850629.py 19
set([(9, 10)])

$ python 1850629.py 21
set([(3, 9, 9)])

$ python 1850629.py 42
set([(3, 9, 10, 10, 10)])

- miku

---

这篇文章被标记为 PHP，只是让你知道一下 :) - Doug Neiner

现在我的时区已经太晚了，应该看书或者睡觉了吧 ;) - miku

Answer 4

有两种明显的方法：

1. 编写一系列线性方程式， 并解决以找到各种解决方案。 选择一个具有最少数量的 术语。
2. 试错法，从最大的项开始。

- Mark Bessey

Answer 5

找出所有可能的解决方案，使得“S=3A+5B+6C+9D+10E”，然后选择具有最多A、B、C、D、E值为0的解决方案。

- Paul Creasey

---

实际上，您想要的解决方案是最小化 A+B+C+D+E。这不一定是具有最多零值的...是吗？ - Stephen C

是的。原始问题的正确关键字是“解决线性丢番图方程”。这是一个重要的研究领域，算法并不简单。例如：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.408 - Matt Kennel

@Stephen 我认为你误读了问题，他想要尽可能少的术语，因此他想要的是最多的零。 - Paul Creasey

Answer 6

除了已经提供的优秀通用答案外，还要记住，如果您的值集具有某些属性，则存在更优化的解决方案。

具体而言，如果您的解决方案是“最小的”-也就是说，任何值都存在一个最佳解决方案-那么您可以使用“贪心”算法找到最少数量的元素：只需添加最大值，直到余数小于它，然后重复使用下一个最大值，以此类推。

例如，许多国家用于货币的面额为0.01、0.02、0.05、0.10、0.20、0.50、1、2、5等。这个集合是最小的，因此您可以重复添加最大的有效面额。

- Nick Johnson

Answer 7

NP完全问题

子集和问题

- Luka Rahne