Zakup Jasia

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/sklep12345678910
język polski13191619191817161514
matematyka18131714151615171817
język angielski17141317161816171817
historia19181713161515161714
plastyka16141718131615161716
geografia17171614151316171816
biologia17141617151613181917
fizyka17161514171615131515
chemia15151618171516151314
muzyka16141618171715161813

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://doktorb.it/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.

Możesz również polubić…

3 komentarze

  1. Paweł Perekietka pisze:

    Zajrzałem do pracy habilitacyjnej.
    W życiu bym nie pomyślał, że w pracy naukowej znajdę tyle rysunków poglądowych:)

  1. 9 września 2021

    […] Zakup Jasia […]

  2. 10 czerwca 2022

    […] Krótka odpowiedź dla większości wydaje się oczywista – kupuj w Internecie. Problem do rozwiązania najlepiej demonstruje zadanie, jakie w 2016 r. mieli do rozwiązania uczestnicy szkolnego konkursu KOALA. […]

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.

The maximum upload file size: 5 MB. You can upload: image, audio, video, document, spreadsheet, interactive, text, archive, code, other. Links to YouTube, Facebook, Twitter and other services inserted in the comment text will be automatically embedded. Drop file here