CODEWITHSUNDEEP
phpalgorithm
user223083
user223083

Reputation:

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=9+9+6
$n=27, S=9+9+9
$n=28, S=10+9+9

Thanks

Upvotes: 4

Views: 409

Answers (7)

Nick Johnson
Nick Johnson

Reputation: 101149

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.

Upvotes: 0

Josh Davis
Josh Davis

Reputation: 28730

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

Upvotes: 2

Luka Rahne
Luka Rahne

Reputation: 10457

NP-complete problem

Subset sum problem

Upvotes: -1

Mark Byers
Mark Byers

Reputation: 838736

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.

Upvotes: 8

miku
miku

Reputation: 188124

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

Upvotes: 0

Paul Creasey
Paul Creasey

Reputation: 28864

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

Upvotes: 0

Mark Bessey
Mark Bessey

Reputation: 19782

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.

Upvotes: 0

Related Questions