Detection if an integer can be written as the sum of given integers

Question

Suppose I have constants 3,5,6,9,10. How can I determine how to write $ n, which is the input, as the sum of these constants with the least number of members?

Examples

$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 

thanks

Answer 1

This is another Python solution, but hopefully it will be easy for you to convert it to PHP (I would do it myself, but I'm not a PHP expert - I’m sure that you could deal with this better). I tried not to use any advanced Python features, so readers who don't use Python are easier to understand, but if some of the Python syntax is not clear, 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, starting from 0 and creating to the desired number, while maintaining the cache of the shortest solution, visible so far for each possible result. It has an O (n * a) runtime, where a is the number of different valid values.

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

Update: here is my attempt to solve 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]); ?> 

It gives the correct answer, but please keep in mind that I am not a professional PHP encoder - I was just looking for equivalent functions in the PHP documentation.

Answer 2

This is Mark Bayer's algorithm rewritten using loop structures more familiar to PHP developers and constructs that will not generate PHP notifications. $C is your set of integers, $S 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]); 

Answer 3

Two obvious approaches involve:

• Write a series of linear equations, and decide to find various solutions. Choose the one with the least number of dates.
• Trial and error starting with the smallest largest members.

Answer 4

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

Answer 5

rough sketch of an immodest 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 

will give:

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

Answer 6

In addition to the excellent general answers already provided, remember that if your set of values ​​has certain properties, there is a much better solution.

In particular, if your solution is "minimal", that is, for any value there is only one better solution - then you can find the smallest number of elements using the "greedy" algorithm: just add the largest value until the remainder is less, repeat with the next big value etc.

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 reuse add the largest legal name.

Answer 7

NP-complete problem

Subset Sum Problem