Обнаружение, может ли целое число быть записано как сумма данных целых

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.

Answer 2

Это алгоритм Марка Байерса, переписанный с использованием структур цикла, более знакомых разработчикам 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]);

Answer 3

В дополнение к уже полученным отличным общим ответам имейте в виду, что если ваш набор значений обладает определенными свойствами, существуют гораздо более оптимальные решения.

В частности, если ваше решение является «минимальным», то есть существует единственное наилучшее решение для любого значения, тогда вы можете найти наименьшее количество элементов, используя «жадный» алгоритм: просто добавьте наибольшее значение, пока остаток не станет меньше его, повторите со следующим наибольшим значением и т. д.

В качестве примера, деноминации, используемые для денег во многих странах: .01, .02, .05, .10, .20, .50, 1, 2, 5, .... Этот набор минимален, поэтому Вы можете просто несколько раз добавить наибольшее действительное наименование.

Answer 4

NP-полная задача

Проблема подмножества сумм

Answer 5

грубый набросок не масштабируемого, но правильного решения (извините, пока это единственный питон ..):

#!/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)])

Answer 6

Найдите все возможные решения для "S = 3A + 5B + 6C + 9D + 10E", затем выберите то, которое имеет наибольшее 0 значений для A, B, C, D, E

Answer 7

Два очевидных подхода предлагают себя:

1. Напишите серию линейных уравнений, и решить, чтобы найти различные решения. Выберите один с наименьшим количеством термины.
2. Метод проб и ошибок, начиная сначала с самыми большими условиями.