[PHP] Knapsack probleem

[Kayshin]

Ik heb het volgende probleem:

Ik heb de volgende lijst (dit is een deel ervan):

Name	Strength	Value
cell attack unit	10	1000 Naquadah
probe attack unit	20	1800 Naquadah
spider attack force	30	3200 Naquadah
ecosystem attack force	60	5100 Naquadah
AI Interfacors	160	16400 Naquadah

Voorwaarden:
Ik heb een vaste hoeveelheid Naquadah the besteden.
Ik mag elk "product" meerdere malen kopen
Ik wil mijn maximale strength eruit halen.

Omdat ik wel iets van wiskunde af weet, maar niet zoveel probeer ik het hier maar eens. Ik wist van mij HBO wiskunde nog dat dit het knapsack probleem is, echter heb ik nergens een fatsoenlijke oplossing in C, C++ of PHP gevonden die dit probleem oplost. Ik ben er ondertussen wel achter dat het een unbounded knapsack probleem is en dat de 0/1 knapsack oplossing (ook wel binair) niet van toepassing is.

Is er iemand (een toevallig langskomend wiskundig genie ofzo ) die me hierbij kan helpen?

[Technicality]

Is het niet gewoon de relatieve strength (dus per Naquadah) uitrekenen en dan zoveel mogelijk daarvan kopen, totdat dat bedrag er niet meer volledig inpast, waarna je naar het goedkopere item gaat om te kijken hoeveel en of je die nog kan kopen? Enige probleem zou dus zijn als je een bedrag overhoud, is dat wat je bedoelt?

[Wolfboy]

Ga deze maar eens lezen: http://www.diku.dk/users/pisinger/95-1.pdf

Technicality, nee, dat is niet de goede oplossing. Daarmee krijg je namelijk niet de efficientste invulling, al komt het wel in de buurt waarschijnlijk.
Om eventjes een voorbeeld te geven, je hebt een max van 11 en items van 3 en 2.
11 - 3 = 8
8 - 3 = 5
5 - 3 = 2
2 - 2 = 0
Zo efficient mogelijk dus.
Maar wat als we nu 10 hebben?
10 - 3 = 7
7 - 3 = 4
4 - 3 = 1
Nu houden we opeens 1 over, het zou efficienter geweest zijn om in plaats van 3 gewoon 2x 2 eraf te halen.

[Kayshin]

Wolfboy schreef op vrijdag 02 februari 2007 @ 02:21:
Ga deze maar eens lezen: http://www.diku.dk/users/pisinger/95-1.pdf

Technicality, nee, dat is niet de goede oplossing. Daarmee krijg je namelijk niet de efficientste invulling, al komt het wel in de buurt waarschijnlijk.
Om eventjes een voorbeeld te geven, je hebt een max van 11 en items van 3 en 2.
11 - 3 = 8
8 - 3 = 5
5 - 3 = 2
2 - 2 = 0
Zo efficient mogelijk dus.
Maar wat als we nu 10 hebben?
10 - 3 = 7
7 - 3 = 4
4 - 3 = 1
Nu houden we opeens 1 over, het zou efficienter geweest zijn om in plaats van 3 gewoon 2x 2 eraf te halen.

Had ik ook al gedownload zo'n half uurtje geleden maar kom er geen wijs uit, ben er te lang niet meer mee bezig geweest

[Soultaker]

Integer knapsack? Oplossen met pseudo-polynomiaal dynamisch programmeren. Zo bijvoorbeeld:

PHP:

// Hoeveel willen we uitgeven?
$money = 12345;

// Definieer beschikbare voorwerpen
$units = 6;
$name     = array( 'Cell', 'Probe', 'Spider', 'Eco',  'AI' );
$strength = array(     10,      20,       30,    60,   160 );
$cost     = array(   1000,    1800,     3200,  5100, 16400 );

// Reken de maximale strength uit.
//  $max_strength[$n] is de maximale strength bereikbaar door $n uit te geven;
//  $to_buy[$n] houdt bij welk item het beste gekocht kan worden, met $n over.
for($u = 0; $u < $units; ++$u)
{
    for($n = $cost[$u]; $n <= $money; ++$n)
    {
        $new_strength = $max_strength[$n - $cost[$u]] + $strength[$u];
        if($new_strength > $max_strength[$n])
        {
            $max_strength[$n] = $new_strength + 1;
            $to_buy[$n] = $u;
        }
    }
}

// Resultaat printen
for($n = $money; $max_strength[$n]; $n -= $cost[$to_buy[$n]])
    echo $name[$to_buy[$n]], "\n";

En neem 'm nu niet direct over, maar probeer eerst te doorgronden hoe/waarom dit werkt. (Overigens heb ik niet getest, dus direct overnemen zou wel eens een slecht idee kunnen zijn...) Als je achtergrondinformatie zoekt, kun je bijvoorbeeld hier kijken voor een goede uitleg: Dynamic Programming - Integer Knapsack. De aanpak heet dynamic programming; daar kun je beter op zoeken dan knapsack problem (daar zijn nogal veel variaties van, en bovendien een heleboel geavanceerde algoritmen voor moeilijkere problemen).

Om de boel efficiënter te maken, is het verstandig om de grootste gemene deler van alle kosten te nemen en alle bedragen (ook het geld wat je hebt te besteden) daar door te delen. In het voorbeeld wat je in de TS geeft, zijn alle bedragen bijvoorbeeld deelbaar door 100; dat scheelt een factor 100 op de running time.

[ Voor 18% gewijzigd door Soultaker op 02-02-2007 03:26 ]