Set Cover Problem met Voorraden

[marco282]

Beste medetweakers,

Voor een website waarmee ik bezig ben loop ik tegen een efficiency probleem aan. Het betreft een website welke virtuele items van games e.d. heeft. Deze virtuele items staan op verschillende accounts(warehouses). Nu als iemand een levering van virtuele items wilt hebben kan het zijn dat de items die deze persoon wilt van verschillende accounts moeten worden afgehaald.

Nu is dit een vrij bekend probleem, zie bijvoorbeeld deze voorbeeld op stackoverflow http://stackoverflow.com/...-from-multiple-warehouses. Hierbij heb ik ookal enkele voorbeelden gevonden om het "minimum set cover" probleem om te lossen zoals een PHP voorbeeld hier http://stackoverflow.com/...897/minimum-set-cover-php.

Je zou denken oh top! kan je gelijk overnemen! maar helaas mist voor mij hier nog een gedeelte. Namelijk de hoeveelheid op voorraad.

Het kan namelijk voorkomen dat "warehouse" 1 10 items van A heeft, en warehouse B heeft er 5.en C heeft er 3. De klant wilt er 11. Dus zou die de gegevens van A en B, of A en C kunnen halen. Maar daarintegen wilt de klant ook nog een ander item hebben die weer anders voorradig is.

Ik zoek dus een algoritme die de beste combinatie van "warehouses" vindt. Dat wil zeggen zo min mogelijk aantal warehousen nodig voor de transactie.

Een PHP voorbeeld van als voorraad geen probleem zou zijn:

PHP:

$MainSet=array(1, 2, 3, 4, 5, 6, 7);
$SubSet=array(array(1,4), array(2, 5), array(3, 6), array(1, 2, 3), array(4, 5, 6));

$UncoveredElements=$MainSet;
$CoveringSets=array();
while (count($UncoveredElements)>0){
    $S=SubSetS($UncoveredElements, $SubSet);
    if (is_array($S)){
        $UncoveredElements=array_diff($UncoveredElements, $S);
        $CoveringSets[]=$S;
    }else
        break; //finish work
}
echo "Sets that cover MainSet are:";
var_dump($CoveringSets);

//Subset S is chosen that covers as many uncovered elements as possible
function SubSetS($UncoveredElements, $SubSetArr){
    $max=0; $s=array();
    foreach($SubSetArr as $SubSet){
        $intersectArr=array_intersect($UncoveredElements, $SubSet);
        $weight=count($intersectArr);
        if ($weight>$max){
            $max=$weight;
            $s=$SubSet;
        }
    }
    if ($max>0)
        return $s;
    else
        return 0;
}

Echter zou bij mij de mainset al een multidimensionale array worden en de subsets zullen arrays van drie diep hebben, voorraad zou namelijk meespelen.

Mijn vraag is nu dus of iemand mij de juiste weg op kan wijzen om dit probleem op te lossen.


Groet
Marco

[pedorus]

Doet me denken aan:

quote: https://xkcd.com/287/

Ik vermoed dat je de code de je gepost hebt zelf niet snapt. Wat je zou kunnen doen is de arrays associative maken (itemnummer => aantal nog nodig / op voorraad). Dan per stapje steeds bepalen welk account in het meeste aantal items weet te voorzien (in functie SubSetS). En dan vervolgens steeds de voorraden van dat account eraf halen totdat je in alles hebt voorzien / er achter komt dat je niet kan voldoen aan de vraag.

Echter, net als met de code waarmee je hier begint is een optimale oplossing niet bepaald gegarandeerd.