Bu başka bir Python bir çözümdür, ancak PHP dönüştürmek için umarım çok kolay (ben kendim yapardım, ama ben hiçbir PHP uzman değilim - Ben bunu daha iyi bir iş yapabileceğini eminim). Ben olmayan Python okuyucular anlamak için daha kolaydır, böylece herhangi bir gelişmiş Python üstlendiği fonksiyonları kullanmaya çalıştı, ancak bazı Python sözdizimi açık değilse, sadece isteyin ettik.

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'dan başlayan ve istenilen numaraya kadar bina, her olası toplamda şimdiye kadar gördüğüm en kısa çözümün bir önbellek tutarak çalışır. Bu O çalışan bir süre (n * a), burada farklı izin verilen değerler sayısıdır.

Bu arada, n = 28 için cevap yanlış. Bu, [9, 9, 10] olmalıdır.

Güncelleme: Burada PHP çözüm benim girişimi:

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

Bu doğru cevabı verir, ama ben profesyonel bir PHP coder değilim lütfen unutmayın - Ben sadece PHP belgelerinde eşdeğer fonksiyonları baktı.

Bu Mark Byers 'PHP geliştiricileri için daha tanıdık döngü yapılarını kullanarak yazılabilir algoritması, ve PHP bildirimleri üretmek değil yapıları olduğunu. $C tamsayılar, $S çözümleri sizin kümesidir.

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

İki belirgin yaklaşımlar kendilerini öneririz:

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.

"S = 3A +5 +6 B C +9 D +10 e" daha sonra A, B, C, D, E için en 0 değerleri ile birini seçmek için mümkün olan tüm çözümleri bulun

Bir tırmanılamaz ancak doğru çözümü kaba bir kroki (üzgünüm, bugüne kadar sadece 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

doğuracak:

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

Değerler set belirli özelliklere sahip olup olmadığını akılda zaten sağlanan mükemmel genel cevaplar, ayı ek olarak, çok daha optimal çözümler var olduğunu.

Çözüm 'minimal' ise Özellikle, - yani, bir tek en iyi çözüm herhangi bir değer için var - o zaman bir 'açgözlü' algoritma kullanılarak elementlerin en küçük sayısını bulabilirsiniz: kalan ondan daha küçüktür kadar Sadece büyük değer katacak , vb sonraki en büyük değeri ile tekrarlayın, ve.

Örnek olarak, birçok ülkede para için kullanılan mezhep .01, .02, .05, .10, .20, .50, 1, 2, 5, .... Bu set yüzden sadece can, minimal arda büyük geçerli mezhep ekleyin.

NP-tam problem

Subset sum problem