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.