Heellou!
En ole varma kuinka aktiivinen Ohjelmointiputka nykyään on mutta nakkaampa pulmani tänne. Elikkäs ongelma, joka itselle on tullut vastaan enkä ole osannut ratkaista on seuraavanlainen; Minulla on neljä eri laatikkoa joissa kussakin on eri sisältöä vaihtelevissa määrissä:
Laatikko A Pikkulaatikko A x 20 Pikkulaatikko B x 10 Pikkulaatikko C x 5 Pikkulaatikko D x 2
Laatikko B Pikkulaatikko B x 15 Pikkulaatikko C x 10 Pikkulaatikko D x 7
Laatikko C Pikkulaatikko A x 5 Pikkulaatikko C x 15 Pikkulaatikko D x 20
Laatikko D Pikkulaatikko A x 5 Pikkulaatikko E x 10
Minulle on esitetty tilaus tietyistä määrästä pikkulaatikoita, mutta tilaukset lähetetään isoissa laatikoissa(Laatikot A, B, C, D).
Kuinka lasken Laatikko A, B, C ja D määrät mahdollisimman lähelle pyydyä tilausta pikkulaatikoita(nollan yläpuolella muttei ali):
Pikkulaatikko A x 300
Pikkulaatikko B x 140
Pikkulaatikko C x 120
Pikkulaatikko D x 70
Pikkulaatikko E x 80
Tämä onkelma on päätä vaivannut pitkään eikä ole ratkennut. Moista ohjelmaa olisin kirjoittamassa eri kielissä ja ongelma on se etten tiedä kuinka moinen laskusuoritus pitäisi kirjoittaa.
Työ kaikkivaltiaat Koodiwelhot ja Matematiikan maisterit kaikki apu otetaan vastaan! Kiitoksia etukäteen!
P.S. Jos kirjoitus on liian epäselvässä muodossa niin voin tarpeen tullen kirjoittaa sen uusiksi eri esimerkkiä käyttäen, mutta ongelma kuitenkin pysyy samana.
Mikä tarkalleen on ”paras” ratkaisu? Pitääkö tavaraa olla mieluummin liikaa vai liian vähän? Onko parempi olla 1×A liikaa vai 1×B liian vähän? Onko parempi olla 2×A liikaa vain 1×A ja 1×B liikaa, vai onko mitään väliä?
Ah! Pahoittelen etten tuota maininnut tarkemmin! Eli täydellinen tulos olisi jossa isompien laatikoiden määrä olisi just eikä melkein, jolloin Pikkulaatikoita olisi tasan tarkalleen pyydetty määrä. Jos moinen ei ole mahdollista niin pikkulaatikoita(pikkulaatikko A, B, C, D, E) voi olla enemmän.
Eli tulos olisi joko tasan pyydetty määrä tai lähin mahdollinen jokaisen pikkulaatikon kohdalla(positiivisena eikä negatiivisena). En ole varma selvensikö kuinka paljon.
Isot laatikot ovat aina kokonaisina eivätkä koskaan desimaaleina
Hyvä algoritmi ongelman ratkaisuun riippuu paljon siitä, millaisia laatikot ja tilaukset ovat tarkalleen.
Jos esimerkki on lähellä todellisuutta, voisi riittää ihan vain käydä läpi kaikki mahdollisuudet valita laatikoita. Voiko esimerkiksi olettaa, että mitään isoa laatikkoa ei tarvita yli 50 kappaletta ratkaisussa?
Monia algoritmeja on olemassa, mutta ensin olisi hyvä tietää tarkat rajoitteet ongelmalle.
Hhmm... no koko homman idea on että isojen laatikkojen on sisältö on aina vakio ja niiden määrälle ei ole mitään max. määrää, mutta tilaajalle annetaan kuitenkin pienin mahdollinen määrä joka täyttää pyydettyjen pienten laatikkojen(A-E) määrät.
Pienten laatikkojen määrät on tilauksissa miljoonissa ja monesti biljoonissa.
Eikö tuo mene lineaarisella Diofantoksen yhtälöllä? Siis jos on A' kpl laatikoita A, B' kpl laatikoita B jne., niin A-laatikoista saadaan yhtälö muotoa 20A+5C+5D=E, ja samoin muille yhtälöille. Lineaarisille Diofantoksen yhtälöille voidaan käyttää Eukleideen algoritmia. Kahden tuntemattoman tapaus tuli aikoinaan lukiossa, useamman muuttujan tapauksessa ainakin Mapleen on koodattu ratkaisija.
Mun mielestä tossa tulee turhaa hankaluutta ymmärtää tehtävä oikein siitä että käytetään samoja kirjaimia isoille ja pienille laatikoille. Miksei isot voisi olla esim. K-N
Eli
K = 20A + 10B + 5C +2D
L = 15B + 10C + 7D
M = 5A + 15C +20D
N = 5A + 10E
Täsmälleenhän noita ei useimmissa tapauksissa saa menemään, mutta jos ymmärsin oikein niin pitäisi saada mahdollisimman pieni ei-negatiivinen määrä K-N, jolla saataisiin pyydetyt A-E:t niin että jotain mahdollisesti jää yli, mutta yhtään ei jää puuttumaan.
Periaatteessa jos on yksinkertainen tapaus, että tarvitaan 100 000 E-laatikkoa, niin lopputulos on että 10 000 N:ää, jolloin jää 50 000 A:ta ylimääräiseksi, mutta E:tä saadaan pyydetty määrä.
Jos taas on toinen yksinkertainent tapaus, että halutaan 100 000 A-laatikkoa, niin kumpi on parempi saada ylimääräisenä:
* 200 000 E
vai
* 50 000 B + 25 000C + 10 000 D
Kiitoksia vinkistä jaska minäpä tarkastelen ja opettelen nuo ja katson jos niillä saisin toimimaan.
Grez, Ei ole itelle tuottanut ongelmia mutta voihan sitä eri kirjaimet laittaa välttääkseen sekavuutta.
Kyllä se olisi erittäin yksinkertainen tapaus jos tarvitaan vain yhtä tyyppiä, mutta useamman kohdalla hankaloittuu ja sen takia täällä.
Toisen tapauksen kohdalla voisi varmaan sanoa että se vaihtoehto joka tuo pienimmän määrän isoja laatikoita.
Nyt tarkennuksen jälkeen matemaattisesti muotoillen ongelma menisi siis näin:
Etsi alla olevaan lausekkeeseen ei-negatiiviset kokonaislukukertoimet K, L, M ja N niin, että annetut minimimäärät objekteille A, B, C, D ja E (kokonaislukuja väliltä [0, 10^12]) täyttyvät ja lausekkeen K+L+M+N arvo on pienin mahdollinen.
K*(20A+10B+5C+2D) + L*(15B+10C+7D) + M*(5A+15C+20D) + N*(5A+10E)
Itse asettaisin ensin N:n alustavan arvon E:n perusteella. Sen jälkeen haarukoisin K:n ja L:n jakautumista B:n perusteella ja edelleen rekursiivisesti muut arvot kohdilleen kokonaisminimiä kohti pyrkien. Joku varmasti tietää fiksumman ratkaisun.
Jos ei bruteforceamista älykkäämpää ratkaisua keksi, niin sitäkin voi tällaisessa tapauksessa varmaan vähän optimoida. Eli jos haetaan vaikka biljoonia laatikoita niin ensin haarukoi 100 miljardin erillä, sitten siitä 10 miljardin, 1 miljardin jne.
Jos nyt tosiaan paras ratkaisu on se, jossa on vähiten isoja laatikoita, aika hyvään (ehkä optimaaliseen?) ratkaisuun voisi päästä seuraavalla algoritmilla:
Algoritmin perustelu:
Testiksi PHP-toteutus:
<?php # Tilaus: $A = 300; $B = 140; $C = 120; $D = 70; $E = 80; # Laskurit: $lA = $lB = $lC = $lD = $lE = 0; # Otetaan A5/E10-laatikoita niin, että E riittää. $l_A5_E10 = ceil(max(0, $E) / 10); $lA += 5 * $l_A5_E10; $lE += 10 * $l_A5_E10; # Otetaan A20/B10/C5/D2-laatikoita niin, että A riittää. $l_A20_B10_C5_D2 = ceil(max(0, $A - $lA) / 20); $lA += 20 * $l_A20_B10_C5_D2; $lB += 10 * $l_A20_B10_C5_D2; $lC += 5 * $l_A20_B10_C5_D2; $lD += 2 * $l_A20_B10_C5_D2; # Otetaan B15/C10/D7-laatikoita niin, että B riittää. $l_B15_C10_D7 = ceil(max(0, $B - $lB) / 15); $lB += 15 * $l_B15_C10_D7; $lC += 10 * $l_B15_C10_D7; $lD += 7 * $l_B15_C10_D7; # Otetaan A5/C15/D20-laatikoita niin, että C ja D riittävät. $l_A5_C15_D20 = ceil(max(0, ($C - $lC) / 15, ($D - $lD) / 20)); $lA += 5 * $l_A5_C15_D20; $lC += 15 * $l_A5_C15_D20; $lD += 20 * $l_A5_C15_D20; # Vaihdetaan A20/B10/C5/D2-laatikoita B15/C10/D7-laatikoiksi, jos voidaan. $tmp = floor(($lA - $A) / 20); $l_A20_B10_C5_D2 -= $tmp; $l_B15_C10_D7 += $tmp; $lA -= 20 * $tmp; $lB += 5 * $tmp; $lC += 5 * $tmp; $lD += 5 * $tmp; # Poistetaan B15/C10/D7-laatikoita, jos voidaan. $tmp = floor(($lB - $B) / 15); $l_B15_C10_D7 -= $tmp; $lB -= 15 * $tmp; $lC -= 10 * $tmp; $lD -= 7 * $tmp; echo "Tilaus:\t$A A\t$B B\t$C C\t$D D\t$E E\n"; echo "Tulos:\t$lA A\t$lB B\t$lC C\t$lD D\t$lE E\n"; echo "Osat:\n"; $l_tot = $l_A20_B10_C5_D2 + $l_B15_C10_D7 + $l_A5_C15_D20 + $l_A5_E10; echo " * $l_A20_B10_C5_D2 × A20/B10/C5/D2\n"; echo " * $l_B15_C10_D7 × B15/C10/D7\n"; echo " * $l_A5_C15_D20 × A5/C15/D20\n"; echo " * $l_A5_E10 × A5/E10\n"; echo "Laatikoita: $l_tot\n";
Toivottavasti antamasi luvut olivat oikeat, koska muuten mietin tätä turhaan. :(
Jaska kirjoitti:
Eikö tuo mene lineaarisella Diofantoksen yhtälöllä?
No ei kai, kun ei välttämättä ole tarkkaa ratkaisua vaan etsitään lähintä suurempaa määrää ja vielä mahdollisimman pienillä kertoimilla.
Jos ymmärsin tuon oikein niin tuo on itseasiassa tapa, joka tuli ensimmäisenä mieleen, mutta en ollut varma oliko se paras mahdollinen taikka yksinkertaisin.
luvuthan voi aina vaihtaa kunhan tekee tuolla algoritmilla ja muistaa täyttää suuremmilla ensin
Metabolix kirjoitti:
Jaska kirjoitti:
Eikö tuo mene lineaarisella Diofantoksen yhtälöllä?
No ei kai, kun ei välttämättä ole tarkkaa ratkaisua vaan etsitään lähintä suurempaa määrää ja vielä mahdollisimman pienillä kertoimilla.
Ajattelin, että tarkkaa ratkaisua ei tarvita vaan kasvatetaan laskuria ja tarkistetaan onko ratkaisu olemassa niin kauan kunnes ratkaisu löytyy.
Kevins16 kirjoitti:
Jos ymmärsin tuon oikein niin tuo on itseasiassa tapa, joka tuli ensimmäisenä mieleen, mutta en ollut varma oliko se paras mahdollinen taikka yksinkertaisin.
luvuthan voi aina vaihtaa kunhan tekee tuolla algoritmilla ja muistaa täyttää suuremmilla ensin
Näyttää, että et ymmärtänyt oikein. Pelkkä suurimpien laatikoiden valitseminen järjestyksessä ei välttämättä ole paras ratkaisu. Algoritmissani on lopussa tuo vaihto- ja vähennysvaihe, joka riippuu käytössä olevista laatikoista.
Jaska kirjoitti:
(13.01.2017 15:18:59): ”– –” Ajattelin, että tarkkaa ratkaisua ei tarvita...
Toinen ongelma on, että Diofantoksen yhtälön ratkaisussa voi olla myös negatiivisia lukuja, jotka eivät ole mielekkäitä tässä tehtävässä.
Antti Laaksonen kirjoitti:
Jaska kirjoitti:
(13.01.2017 15:18:59): ”– –” Ajattelin, että tarkkaa ratkaisua ei tarvita...
Toinen ongelma on, että Diofantoksen yhtälön ratkaisussa voi olla myös negatiivisia lukuja, jotka eivät ole mielekkäitä tässä tehtävässä.
Juu. Huomasin itsekin. Ajattelin tätä huomiota ehkä turhan triviaalina. Pitää siis rajoittua epänegatiivisiin ratkaisuihin.
Metabolix kirjoitti:
(13.01.2017 16:26:42): ”– –” Näyttää, että et ymmärtänyt oikein. Pelkkä...
Ymmärsin ymmärsin, mutta kuten on saattanut aikaisemmista kirjoituksistani huomata niin kirjoitan sanomani jokseenkin epäselvästi.
Mikäli haluttaisiin optimoida pienten laatikoiden lukumäärä, riittäisi hakea luonnollisilla luvuilla ratkaisua seuraavaan optimointiongelmaan:
min 37A + 32B + 40C + 15D s.t. 4A + C + D >= 60 2A + 3B >= 28 A + 2B + 3C >= 24 2A + 7B + 20C >= 70 D >= 8
Ohessa vielä toteutus.
def f(A,B,C,D):
#pienet laatikot
return 37*A + 32*B + 40*C + 15*D;
#isot laatikot
#return A + B + C + D
if __name__ == "__main__":
minimum = float('Inf');
for A in range(35+1):
for B in range(12+1):
for C in range(60+1):
for D in range(8,60+1):
if (
4*A + C + D >= 60 and
2*A + 3*B >= 28 and
A + 2*B + 3*C >= 24 and
2*A + 7*B + 20*C >= 70
):
if f(A,B,C,D) < minimum:
minimum = f(A,B,C,D);
A1 = A;
B1 = B;
C1 = C;
D1 = D;
a = 20*A1 + 5*C1 + 5*D1;
b = 10*A1 + 15*B1;
c = 5*A1 + 10*B1 + 15*C1;
d = 2*A1 + 7*B1 + 20*C1;
e = 10*D1;
print "min: " + str(minimum);
print "A: " + str(A1) + " B: " + str(B1) + " C: " + str(C1) + " D: " + str(D1);
print "a: " + str(a) + " b: " + str(b) + " c: " + str(c) + " d: " + str(d) + " e: " + str(e);min: 753
A: 13 B: 1 C: 3 D: 8
a: 315 b: 145 c: 120 d: 93 e: 80
Pythonissa ei tarvita puolipisteitä rivien perään ellei halua sovittaa useampaa riviä yhdelle riville. Voit myös käyttää itertoolsin productia yksinkertaistamaan sisäkkäisten silmukoiden kirjoittamista.
Jaska kirjoitti:
Pythonissa ei tarvita puolipisteitä rivien perään ellei halua sovittaa useampaa riviä yhdelle riville. Voit myös käyttää itertoolsin productia yksinkertaistamaan sisäkkäisten silmukoiden kirjoittamista.
Ok. Lisäksi esim. silmukoiden kokoja voitaisiin varmasti vielä optimoida (nyt käytössä karkeahkot raja-arvot). Lisäsin koodiin rivin f()-funktioon, jolla saadaan optimitulos isojen laatikoiden määrässä (kysyjän alkuperäinen toivomus).
Jaska kirjoitti:
Pythonissa ei tarvita puolipisteitä rivien perään ellei halua sovittaa useampaa riviä yhdelle riville. Voit myös käyttää itertoolsin productia yksinkertaistamaan sisäkkäisten silmukoiden kirjoittamista.
Puolipisteet ovat pelkkä tyyliseikka, mutta niiden kirjoittaminen on täysin sallittua.
Eikö tuo mpnin toteutus ole muuten vain brute-force? Se ei auttane, jos laatikoita tarvitaan biljoonia.
fergusq kirjoitti:
Puolipisteet ovat pelkkä tyyliseikka, mutta niiden kirjoittaminen on täysin sallittua.
Juu, yhtä lailla voi kirjoittaa vaikka 7 puolipistettä vastaaviin paikkoihin - sekin on täysin sallittu "tyyliseikka".
Aihe on jo aika vanha, joten et voi enää vastata siihen.