Zakup Jasia
Zakup Jasia zlecony przez mamę
– Posłuchaj mnie synu – przemówiła matka – Mamy dla ciebie zadanie.
– Słucham – Jasiu niechętnie oderwał się od ulubionej gry.
– Możesz trochę zarobić – usłyszał, co wywołało ożywienie na jego twarzy.
– A ile i co mam zrobić?
– Kupisz sobie podręczniki szkolne, a zarobisz tyle ile ci zostanie z dwustu złotych jakie ci daję na to – matka przekazała Jasiowi banknot.
– To pewnie kupię w sklepie internetowym, bo tam najtaniej – Jasiu porzucił grę i włączył przeglądarkę internetową.
– To dobry pomysł na zakup Jasia – uśmiechnęła się mama.
Rozpoznawanie
Jasiu zaczął przeglądać sklepy internetowe i znalazł ich dziesięć. Okazało się, że w każdym z 10 sklepów internetowych cena każdej z książek jest nieco inna.
| przedmiot/sklep | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| język polski | 13 | 19 | 16 | 19 | 19 | 18 | 17 | 16 | 15 | 14 |
| matematyka | 18 | 13 | 17 | 14 | 15 | 16 | 15 | 17 | 18 | 17 |
| język angielski | 17 | 14 | 13 | 17 | 16 | 18 | 16 | 17 | 18 | 17 |
| historia | 19 | 18 | 17 | 13 | 16 | 15 | 15 | 16 | 17 | 14 |
| plastyka | 16 | 14 | 17 | 18 | 13 | 16 | 15 | 16 | 17 | 16 |
| geografia | 17 | 17 | 16 | 14 | 15 | 13 | 16 | 17 | 18 | 16 |
| biologia | 17 | 14 | 16 | 17 | 15 | 16 | 13 | 18 | 19 | 17 |
| fizyka | 17 | 16 | 15 | 14 | 17 | 16 | 15 | 13 | 15 | 15 |
| chemia | 15 | 15 | 16 | 18 | 17 | 15 | 16 | 15 | 13 | 14 |
| muzyka | 16 | 14 | 16 | 18 | 17 | 17 | 15 | 16 | 18 | 13 |
Jasiu próbował najpierw kupić wszystkie podręczniki w jednym sklepie jednak wszędzie było na tyle drogo, że niewiele mógłby zaoszczędzić. Próbował więc kupować każdy z podręczników w najtańszym dla niego sklepie, ale to powodowało, że każdy musiał kupować w innym i koszty dostawy (po 4 zł) doliczały się z każdego sklepu, a więc w rezultacie musiałby zapłacić 10 · (13 + 4) = 170. Wtedy postanowił spróbować podzielić zakupy na kilka paczek, z których każda byłaby zamawiana z innego sklepu.
Zadanie do rozwiązania – zakup Jasia
Pomóż Jasiowi wybrać sklepy tak, by koszt zakupów książek był jak najmniejszy i by jak najwięcej zaoszczędził.
Zadanie było użyte w I-szym etapie konkursu KOALA edycja III z roku 2015/2016 https://bezkomputera.wmi.amu.edu.pl/koala/koala3_1.pdf
Adam Wojciechowski https://sin.put.poznan.pl/people/details/adam.wojciechowski wpadł na pomysł takiego zadania i traktowania koszykowego zakupu jako optymalizacji kombinatorycznej.
Artykuł wprowadzający do zagadnienia: https://andrzeju.pl/kupowanie-w-sieci-calego-koszyka-towarow-jak-najtaniej/
Praca habilitacyjna Jędrzeja na ten temat: Jędrzej Musiał „Kombinatoryczne modele i algorytmy różnych wariantów problemu optymalizacji zakupów internetowych”, rozprawa habilitacyjna, Poznań, 2018, http://www.cs.put.poznan.pl/jmusial/pubs/20_Musial.pdf
Zapraszam do wpisywania w komentarzach odpowiedzi. Ile optymalnie mógł zaoszczędzić, czyli mieć dla siebie, Jasiu?
Wskazówka
Kto pomoże Jasiowi dokonać zakupu podręczników szkolnych tak by jak najwięcej zaoszczędzić dla siebie?
Trzeba z tablicy 10 x 10 wybrać po jednym elemencie z wiersza tak by ich suma + 4 * liczba zajech kolumn były jak najmniejsze.
Zajrzałem do pracy habilitacyjnej.
W życiu bym nie pomyślał, że w pracy naukowej znajdę tyle rysunków poglądowych:)