Tytuł absurdalny, wszystko dla was, ponieważ zadań z algorytmów nigdy dość! Z okazji Tłustego Czwartku łapcie tematyczne zadanka do rozwiązania jak zwykle w Pythonie (lub dowolnie innym języku programowania).
Wysiłek umysłowy spala kalorie, także po wszystkim możecie się sowicie nagrodzić tłustym pączkiem!
Pączek, kawa i kod… a Python poleca się każdego dnia! 😉
Zadanie 1 – teoria
Chcesz zjeść jak najwięcej pączków w Tłusty Czwartek. Niestety, doświadczenie z poprzednich lat mówi Ci, że pół kilo pączków to maksymalna objętość Twojego żołądka, więc nie masz szans zjeść wszystkich smaków. Twój cel to zjeść jak najwięcej kalorii (wg zasady najpierw masa, potem rzeźba 😉 ), dlatego przed wyborem smaków analizujesz ich wagę i wartość kaloryczną, aby najeść się do syta.
Na stole czekają na ciebie pączki w różnych smakach:
- pączek wiśniowy ok. 100g (252 kcal)
- fit pączek gryczany ze śliwkami ok. 200g (205 kcal)
- pączek z czekoladą ok. 150 g (315 kcal)
- pączek z karmelowo-orzechowy ok. 100 g (441 kcal)
- oreo donut ok. 150 (630 kcal)
- mini pączek z budyniem 50g (126kcal)
Dla ułatwienia pączki numerujesz od 0 do 5 i wszystko skrupulatnie zapisujesz w tabeli
| nr pączka (i) | 0 | 1 | 2 | 3 | 4 | 5 |
| waga pączka (wi) | 100 | 200 | 150 | 100 | 150 | 50 |
| wartość kcal(vi) | 252 | 205 | 315 | 441 | 630 | 126 |
Które pączki musisz zjeść, aby wartość kaloryczna była jak największa?
Zadanie rozwiązać możesz na kartce tworząc tablicę problemu.
(podpowiedź: wykorzystaj programowanie dynamiczne)
Zadanie 2 – python: programowanie dynamiczne, problem plecakowy
Nie będziesz przecież co roku liczyć kalorii na kartce! Wystarczy ten problem zapisać jako decyzyjny inaczej zero-jedynkowy problem plecakowy (0-1 Knapsack Problem). Stwórz program implementujący algorytm programowania dynamicznego (dla chętnych: algorytm zachłanny).
- Pozwól użytkownikowi wprowadzić indywidualną pojemność żołądka (C) oraz elementy — pączki (z wagą i wartością energetyczną) z klawiatury.
- Pozwól użytkownikowi wczytać dane z pliku. Format powinien być zdefiniowany i wyjaśniony na wstępie.
- Program powinien być odporny na podstawowe błędy (np. wczytanie danych o złym typie np. kalorie podane jako string).
Przetestuj swój program ręcznie lub napisz generator pączków.
Dla chętnych: porównaj czas działania algorytmu zachłannego i dynamicznego (porównaj tylko działanie algorytmów bez czasy wczytania danych czy wyświetlenia danych).
Fakt, że tu jesteście sprawia, że jesteście chętni prawda?
python snake loves donuts ❤
Ma ktoś może rozwiązanie pierwszego problemu ?
Proszę o doprecyzowanie. Mam na talerzu te 6 rodzajów pączków po jednej sztuce i tym musze się napchać? Czy mam menu z 6 pozycjami i mogę wybrać kilka takich samych pączków majac na uwadze pojemnosc zoladka i żądze kalorii?
6 pączków jako sztuki, ale to zadanie ćwiczeniowe, nie zaszkodzi zrobić sobie też wersji, że to 6 rodzajów, a możesz każdego rodzaju dobrać ile chcesz (chociaż rozwiązanie byłoby proste – n X pączek o najwyższej gęstości kalorii na masę
w przypadku założenia, że to 6 rodziajów w nieskończonej ilości rozwiązanie jest chyba bardziej skopmplikowane – w podanym przypadku największa ilość kalorii wychodzi przy zestawie 2x paczek 3 + 2x paczek 4. Wg algorytmu n X pączek o najwyższej gęstości kalorii na masę uzyskamy niższy wynik (czyli 3x paczek 4 + 1x paczek 5).
O, fajne zadania optymalizacyjne. Można dość łatwo je rozwiązać algorytmem simplex (napisanym samemu albo wykorzystując bibliotekę PuLP).