Søg
Avatar billede learner Praktikant
31. marts 2011 - 14:01 Der er 15 kommentarer og
1 løsning

funktion der fordeler produkter i kasser efter vægt

Hejsa

Jeg sidde rog skal til at lave en funktion der hjælper vores pakkeri.

Jeg vil lave en funktion der lister varene som de skal pakkes. Dvs at den skal faktisk skille ordren ad i enkeltdele og forsøge at pakke det optimalt efter vægt de enkelte produkter har.

fx hvis der er flg ordre:
2 x 20 kg
3 x 9 kg
3 x 3 kg
6 x 0,5 kg

og der må max være 30 kg i en kasse.

Så skal den skille det ad og liste det påny således at det er nemt for pakkeriet at se hvad der skal være i kasse 1, 2 osv og samtidig bruge så få kasser som muligt.

Jeg har tænkt og tænkt og så er det jeg tænker at der måske findes en PHP funktion som kan benyttes på en smart måde

Forestiller mig at lave et array med produkt id, antal og vægt og så måske benytte en snild metode til at dele produkterne ud i kasserne.

Muligt? Hvordan?
Avatar billede learner Praktikant
31. marts 2011 - 17:00 #1
den skal jo sådan set skabe scenarier med så meget som muligt i kasse 1 og så meget som muligt i kasse 2 osv

jeg tænker at sortere det tungeste først og så gå fremad?

2 x 20 kg
3 x 9 kg
3 x 3 kg
6 x 0,5 kg

er jo

20 kg
20 kg
9 kg
9 kg
9 kg
3 kg
3 kg
3 kg
0,5 kg
0,5 kg
0,5 kg
0,5 kg
0,5 kg
0,5 kg

så tager den den første 20 kg og.... ja hvad skal den så?? :o)
Avatar billede learner Praktikant
31. marts 2011 - 17:04 #2
den nupper den første 20 kg og skal derefter forsøge at ramme så tæt på 10 kg som muligt.

det kan den gøre ved at finde alle varer <= 10 kg som er:
9 kg
9 kg
9 kg
3 kg
3 kg
3 kg
0,5 kg
0,5 kg
0,5 kg
0,5 kg
0,5 kg
0,5 kg

men så står jeg af her :o)
Avatar billede alphabits Nybegynder
31. marts 2011 - 17:21 #3
Ok ronols kom mig i forkøbet, men her får du mit bud:
Du kan løse det med en grådig algoritme:
[code]function create_packages($weights, $max_package_weight) {
    $packages = array();
   
    while (count($weights) > 0) {
        $cur_package = array();
        $cur_weight_left = $max_package_weight;
        $keys = array_keys($weights);
        foreach ($keys as $k) {
            $w = $weights[$k];
            if ($cur_weight_left >= $w) {
                $cur_package[] = $w;
                $cur_weight_left -= $w;
                unset($weights[$k]);
            }
        }
        $packages[] = $cur_package;
    }
   
    return $packages;
}

$weights = array(20,20,9,9,9,3,3,3,0.5,0.5,0.5,0.5,0.5,0.5);

print_r(create_packages($weights, $max_weight));[/code]

Kort fortalt bliver den ved med at fylde i kasser til der ikke er flere varer. Hver gang den starter på en ny kasse, løber den igennem alle varer (der er sorteret med den tungeste først), og hvis der plads i kassen til varen, bliver den smidt i kassen. Bemærk at funktionen jeg har lavet antager at varenes vægt er sorteret med den tungeste først, og at der ikke er nogle varer der vejer mere en den maksimale pakkevægt. Hvis der er en vare der vejer mere end maksvægten vil funktionen loope uendeligt. Koden er kun til at komme igang :)
Avatar billede olsensweb.dk Ekspert
31. marts 2011 - 17:14 #4
jeg har ikke kendskab til nogle predefineret function men et hurtigt forsøg vil se sådan ud
<!DOCTYPE html>
<html>
<head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8"/>
    <title></title>    
</head>
<body>
<?php
function CalcBoxes($boxarray, $MaxWeightPerBox=30){
    $packList = array();
    
    // sorterer efter størrelse, så mindste først
    asort($boxarray);
    // http://php.net/manual/en/function.array-values.php
    // array_values() returns all the values from the input array and indexes numerically the array. 
    $boxarray = array_values($boxarray);
    print_r($boxarray);
    $lng = count($boxarray);
    $sum = 0;
    $notfinish = 1; // et eller andet forskelligt fra 0
    $box = array();
    while($notfinish){        
        for($i=$lng-1; $i>=0; $i--){
            if( $boxarray[$i] < $MaxWeightPerBox && ($sum + $boxarray[$i] <= $MaxWeightPerBox) && $boxarray[$i] !=0){ 
                $box[]= $boxarray[$i];
                $boxarray[$i]=0;
            }
            $sum= array_sum($box);
        }
        $packList[]=$box;
        echo $sum; // test, udskriver vægten på kassen
        // tømmer arrayet
        $boxlng = count($box);
        for($i=$boxlng; $i>=0; $i--){
            array_pop($box);        
        }
        $notfinish = array_sum($boxarray);        
    }    
    // test
    echo $notfinish;    
    print_r($boxarray);
    print_r($packList);
}
$ar= array("20", "20", "9", "9", "9", "3", "3", "3", "0.5", "10", "0.5", "0.5", "0.5", "0.5", "0.5");
CalcBoxes($ar);
?>
</body>
</html>
Avatar billede learner Praktikant
31. marts 2011 - 17:18 #5
Hej Ronols

Den skal jeg da 100% sikkert lege lidt med :o)
vender lige tilbage....
Avatar billede learner Praktikant
31. marts 2011 - 17:38 #6
Hej alphabits
også tak for dit bidrag som vist kan ca det samme :o)
Jeg gad dog godt hvis den laver lidt mere simulering så den "tænker lidt mere"

tag fx denne udfordring:
25
23
4
3
2,5
2

der vil resultatet blive 3 kasser men den kan jo rent faktisk pakkes i 2 kasser :o)
Avatar billede learner Praktikant
31. marts 2011 - 21:40 #7
Er det for svært? ;o) :D

Jeg har i hvert fald ikke udtænkt en metode til at opstille det.

Man kan selvfølgelig argumentere for at det er et over kill, men det må da være muligt at lave på en snu måde
Avatar billede alphabits Nybegynder
31. marts 2011 - 21:59 #8
Det er ikke for svært. Det er umuligt :o) Problemet du prøver at løse hedder (ikke overraskende) bin-packing problemet, og er et såkaldt NP-komplet problem. På dansk betyder det at der ikke findes nogen algoritme der giver det optimale antal kasser, for et vilkårligt input. Du kan læse lidt om det her: http://en.wikipedia.org/wiki/Bin_packing_problem
Når det så er sagt, kan der helt sikkert godt skrives et program der klarer det bedre, end det jeg skrev i forrige indlæg, men du vil altså ikke kunne finde et der er 100% optimalt.
Avatar billede learner Praktikant
31. marts 2011 - 22:05 #9
meget interessant :D
nu føler jeg mig ikke helt så dum hehe :o)
Avatar billede learner Praktikant
01. april 2011 - 10:32 #10
man kunne måske lave den sådan at den i det mindste prøver bare lidt forskellige muligheder af inden den træffer beslutningen.

Jeg har forsøgt mig lidt og håber på at få lidt hjælp med at se på det

<?php


function tep_if_weight_is_null_set_standard($weight){
    if ($weight>0){
        return $weight;
    } else {
        return SHIPPING_STANDARD_WEIGHT_IF_NULL;
    }
}

function tep_weight_incl_tara_weight($total_weight) {
    if ((($total_weight*SHIPPING_BOX_PADDING)/100) > SHIPPING_BOX_WEIGHT) {
        return ($total_weight + (($total_weight*SHIPPING_BOX_PADDING)/100));
    } else {
        return ($total_weight+SHIPPING_BOX_WEIGHT);
    }
}

function tep_simulate_packing($productsList, $return_as='num_boxes'){
    $packList = array();
    $weightarray = array();
   
    // just in case....
    if (!is_array($productsList)) return 1;
   
    foreach ($productsList as $pID => $pQty){
        $total_weight += ($pQty * tep_if_weight_is_null_set_standard(tep_get_products_whatever($pID, 'products_weight')));
        while ($pQty>0){
            $weightarray[$pID][] = tep_if_weight_is_null_set_standard(tep_get_products_whatever($pID, 'products_weight'));
            $mirror_weightarray[tep_if_weight_is_null_set_standard(tep_get_products_whatever($pID, 'products_weight'))][] = $pID;
            $pQty--;
        }
    }
   
    // vi afgør om der skal laves mere end 1 pakke
    if (tep_weight_incl_tara_weight($total_weight) > SHIPPING_MAX_WEIGHT) { // Split into many boxes
        arsort($weightarray); // sorterer efter størrelse, så største først
        $weightarray = array_values($weightarray); // array_values() returns all the values from the input array and indexes numerically the array.
        $lng = count($weightarray);
        $sum_total = 0;
        $notfinish = 1;
        while($notfinish){       
           
            for($ii=$lng-1; $ii>=0; $ii--){
                $simulate_weightarray = $weightarray;
                $sum = 0;
                $box = array();
               
                // vi vælger et produkt og forsøger derefter at fylde resten af pladsen op
                $box[] = $simulate_weightarray[$ii];
                $simulate_weightarray[$ii]=0;
                $best_sum = 0;
                $best_box = array();
               
                while($sim_notfinish){   
                    // prøver at sætte den sammen med forskellige produkter
                    for($i=$lng-1; $i>=0; $i--){
                        if( tep_weight_incl_tara_weight($simulate_weightarray[$i]) < SHIPPING_MAX_WEIGHT && (tep_weight_incl_tara_weight($sum + $simulate_weightarray[$i]) <= SHIPPING_MAX_WEIGHT) && $simulate_weightarray[$i] !=0){
                            $box[] = $simulate_weightarray[$i];
                            $simulate_weightarray[$i]=0;
                        }
                        $sum = array_sum($box); // vægten på kassen
                    }
                    if (array_sum($box)>$best_sum){
                        $best_sum = array_sum($box);
                        $best_box = $box;
                    }
                    $sim_notfinish = array_sum($simulate_weightarray);       
                }
            }
            $packList[]     = $best_box;
            $WeightList[]     = $best_sum; // vægten på kassen
            // tømmer arrayet
            $boxlng = count($box);
            for($i=$boxlng; $i>=0; $i--){
                array_pop($box);       
            }
            $notfinish = array_sum($weightarray);       
        }   
        $num_boxes = count($packList);
    } else {
        arsort($weightarray); // sorterer efter størrelse, så største først
        $weightarray = array_values($weightarray); // array_values() returns all the values from the input array and indexes numerically the array.
       
        $num_boxes         = 1;
        $packList[]     = $weightarray;
        $WeightList[]     = tep_weight_incl_tara_weight($total_weight); // vægten på 1 kasse
    }
   
    // list produkterne som skal i pakkerne
    $packingList = array(array());
    foreach ($packList as $box_number => $a_box){
        foreach ($a_box as $weight)
            $packingList[$box_number][] = $mirror_weightarray[$weight][0];
            // fjerner produktet, så det kun lægges i kassen denne ene gang (ved ik om det virker efter hensigten)
            array_pop($mirror_weightarray[$weight]);
            if (is_array($mirror_weightarray[$weight])) $mirror_weightarray[$weight] = array_values($mirror_weightarray[$weight]); // rykker nr
            // her kunne evt bruges next() i stedet for
        }
    }
   
    if ($return_as=='num_boxes')    return $num_boxes;
    if ($return_as=='packList')        return $packingList;
    if ($return_as=='WeightList')    return $WeightList;
}
 
$productsList = array(133=>1,144=>1,122=>1,111=>1,166=>1,177=>1); // vægten er : 133=>25 kg, 144=>23 kg, 122=>4 kg, 111=>3 kg, 166=>2.5 kg, 177=>2.5 kg
echo tep_simulate_packing($productsList, 'num_boxes');


?>
Avatar billede olsensweb.dk Ekspert
01. april 2011 - 16:32 #11
jeg har lavet en forsøg hvor jeg afprøver 3 forskellige motoder, og ligger resultaterne i et multi array, som jeg derefter sorterer, for at finde den bedste (færrest kasser)

<?php
function ClearBox(&$box){
    // tømmer arrayet / kassen
    $lng = count($box)-1;
    for($i=$lng; $i>=0; $i--){
        array_pop($box);        
    }        
}
function CalcBoxes($boxarray, $MaxWeightPerBox=30){
    $packList = array();
    $lng = count($boxarray);    
    $notfinish = array_sum($boxarray);        
    $box = array();
    while($notfinish){        
        $sum = 0;    
        for($i=0; $i<$lng; $i++){
            if( ($boxarray[$i] < $MaxWeightPerBox) && ($sum + $boxarray[$i] <= $MaxWeightPerBox) && ($boxarray[$i] != 0) ){ 
                $box[]= $boxarray[$i];
                $sum += $boxarray[$i];
                $boxarray[$i]=0;
            }            
        }        
        $packList[]=$box;        
        $notfinish = array_sum($boxarray);        
        ClearBox($box);        
    }    
    return $packList;    
}
function CalcBoxes_HeaviestLightest($boxarray, $MaxWeightPerBox=30){
    $packList = array();
    $lng = count($boxarray)-1;    
    $notfinish = array_sum($boxarray);        
    $box = array();    
    $i=0;
    while($notfinish){        
        $sum = 0;            
        for(; $i<=$lng;){                        
            if( ($boxarray[$i] < $MaxWeightPerBox) && ($sum + $boxarray[$i] <= $MaxWeightPerBox) && ($boxarray[$i] != 0) ){ 
                $box[]= $boxarray[$i];
                $sum += $boxarray[$i];
                $boxarray[$i]=0;
                $i++;
            }                
            if( ($boxarray[$lng] < $MaxWeightPerBox) && ($sum + $boxarray[$lng] <= $MaxWeightPerBox) && ($boxarray[$lng] != 0) ){
                $box[]= $boxarray[$lng];
                $sum += $boxarray[$lng];                
                $boxarray[$lng]=0;                
                $lng--;
            }
            else break;            
        }        
        $packList[]=$box;            
        $notfinish = array_sum($boxarray);        
        ClearBox($box);        
    }    
    return $packList;    
}
function CalcBoxes_HeaviestSteep2($boxarray, $MaxWeightPerBox=30){
    $packList = array();
    $lng = count($boxarray)-1;    
    $notfinish = array_sum($boxarray);        
    $box = array();    
    $j=0;
    while($notfinish){        
        $sum = 0;            
        for($i=$j; $i<=$lng; $i+=2){                        
            if( ($boxarray[$i] < $MaxWeightPerBox) && ($sum + $boxarray[$i] <= $MaxWeightPerBox) && ($boxarray[$i] != 0) ){ 
                $box[]= $boxarray[$i];
                $sum += $boxarray[$i];
                $boxarray[$i]=0;                
            }                
        }        
        $packList[]=$box;            
        $notfinish = array_sum($boxarray);        
        ClearBox($box);        
        $j++;
    }    
    return $packList;    
}
//$ar= array(20, 20, 9, 9, 9, 3, 3, 3, 0.5, 10, 0.5, 0.5, 0.5, 0.5, 0.5);
$ar = array(25,23,4,3,2.5,2);
// sorterer efter størrelse, så størreste først
arsort($ar);
$ar = array_values($ar);
print_r($ar);    
$attempts = array();        
$liste = CalcBoxes($ar);
$antal = count($liste);
$txt = "hele tiden tungeste først";
$attempt = array($txt, $antal, $liste);
$attempts[] = $attempt;    
$liste = CalcBoxes_HeaviestLightest($ar);
$antal = count($liste);    
$txt = "tungeste først derefter letteste";
$attempt = array($txt, $antal, $liste);
$attempts[] = $attempt;        
$liste = CalcBoxes_HeaviestSteep2($ar);
$antal = count($liste);    
$txt = "tungeste først steep 2";
$attempt = array($txt, $antal, $liste);
$attempts[] = $attempt;    
foreach ($attempts as $key => $row) {
    $at[$key]  = $row[1]; // of course, replace 0 with whatever is the date field's index
}
array_multisort($at, SORT_ASC, $attempts);    
print_r($attempts[0]);    // bedste
// print_r($attempts); // alle    
?>
Avatar billede learner Praktikant
01. april 2011 - 18:48 #12
:o) :o) :o)

TUUUUSIND tak
Det er virkelig interessant

Jeg vil kigge på det og vende tilbage.

Kæresten kalder :o)
Avatar billede learner Praktikant
04. april 2011 - 10:27 #13
udsat lidt pga tidspres - jeg vender tilbage ASAP
Avatar billede learner Praktikant
14. april 2011 - 01:04 #14
projektet er sat lidt på pause, men jeg genoptager det 100% sikkert og håber at det ender med en god løsning
Avatar billede learner Praktikant
05. oktober 2012 - 15:13 #15
Hej - længe siden, og jeg har sidenhen været til foredrag om det her - spændende problem/udfordring. Nogen af disse relativt enkle simuleringsopgaver tager op til mange gange universets levetid at beregne/simulere, selv med supercomputere. Meget interessant.

Måske en gang man kan oversætte svære matematiske opgaver til en særlig form, og så ændre det til bølger eller noget fysisk, som så kan tolkes/tilbagedannes/oversættes tilbage til et matematisk svar.

Virkelig spændende..

Nå men jeg løste pakke opgaven ved ikke at løse den :o)
Jeg tager bare samlet vægt divideret med max vægt pr pakke, og så får jeg antal pakker. Jeg beregner ikke hvordan varene skal fordeles - det lader jeg pakkerimedarbejderen om. Så har de også lidt indflydelse på deres arbejde ;o)

De enkelte gange hvor der sker en fejl, så tager vi den manuelt. Og nu har systemet kørt i over et år uden at der er nogen fejl :o)

Hvis nogen ønsker point, så smid lige et svar

Tak for hjælpen allesammen
Avatar billede olsensweb.dk Ekspert
05. oktober 2012 - 20:01 #16
svar
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Webudvikling kurser
Vi tilbyder markedets bedste kurser inden for webudvikling
Se alle Webudvikling kurser

Flere spørgsmål fra PHP kategorien

Titel Indlæg Oprettet Seneste aktivitet
Hvordan får jeg reCAPTCHA på min hjemmeside? Af Strawberry i PHP 0 20/01/202621:11 -
MS Graph vis kalenderaftaler Af dane022 i PHP 0 06/11/202508:43 -
Hente data fra DEVICE via websocket Af nemlig i PHP 6 25/06/202512:37 25/06/202519:17
Login og redirect Af hrole i PHP 3 24/06/202518:52 24/06/202523:37
Batflat CMS Af sabumnim i PHP 0 06/06/202512:37 -
Se alle spørgsmål i kategorien Opret spørgsmål

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Opret Log ind

Du kan også logge ind via nedenstående tjenester

Alle kategorier på Eksperten
Seneste spørgsmål Seneste aktivitet
I går 20:51 Knap til ipad Af FinnLauridsen i Excel
21/0113:53 Icloud mail via Outlook Af lbc i E-mail programmer
21/0108:32 USB NØGLE gratis Af nu_igen i Andet hardware
20/0121:11 Hvordan får jeg reCAPTCHA på min hjemmeside? Af Strawberry i PHP
20/0116:10 Tomt felt i Start Af ErikHg i Windows
White papers
Flere white papers »