Detecting if integer can be written as sum of given integers

Supposing I'm having the constants 3,5,6,9,10. How can I detect how to write $n, which is the input, as a sum of these constants with the least number of terms?

Examples

$n=10, S=10
$n=18, S=9+9
$n=24, S开发者_如何学C=9+9+6
$n=27, S=9+9+9
$n=28, S=10+9+9

Thanks

---

This is another Python solution, but hopefully it's easy for you to convert to PHP (I would do it myself, but I'm no PHP expert - I'm sure you could do a better job of it). I've tried not to use any advanced Python funcitons, so that it is easier for non-Python readers to understand, but if some Python syntax is not clear, please just ask.

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]

It works by starting from 0 and building up to the desired number, keeping a cache of the shortest solution seen so far for each possible total. It has a running time of O(n * a), where a is the number of different allowed values.

By the way, your answer to n=28 is wrong. It should be [9, 9, 10].

Update: here's my attempt at a PHP solution:

<?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]);
?>

It gives the right answer, but please be aware that I'm not a professional PHP coder - I just looked up the equivalent functions in the PHP documentation.

---

This is Mark Byers' algorithm, rewritten using loop structures that are more familiar to PHP developers, and constructs that won't generate PHP notices. $C is your set of integers, $S the solutions.

$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]);

---

Two obvious approaches suggest themselves:

1. Write a series of linear equations, and solve to find various solutions. Choose one with the least number of terms.
2. Trial and error, starting with the largest terms first.

---

Find all possible solutions for "S=3A+5B+6C+9D+10E" then choose the one with the most 0 values for A,B,C,D,E

---

a rough sketch of an unscalable but correct solution (sorry, so far its only 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

would yield:

$ 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)])

---

In addition to the excellent general answers already provided, bear in mind that if your set of values has certain properties, much more optimal solutions exist.

Specifically, if your solution is 'minimal' - that is, a single best solution exists for any value - then you can find the smallest number of elements using a 'greedy' algorithm: Simply add the largest value until the remainder is smaller than it, repeat with the next largest value, and so forth.

As an example, the denominations used for money in many countries are .01, .02, .05, .10, .20, .50, 1, 2, 5, .... This set is minimal, so you can just repeatedly add the largest valid denomination.

---

NP-complete problem

Subset sum problem