Mam ogromny problem, wierzę, że na tym forum znajdzie się ktoś kto może mi pomóc. Mój kierunek studiów kompletnie nie wiąże się z informatyką, ale los chciał, że dostałam do zrobienia zadanie, które dla mnie wydaje się być nierozwiązywalne. Mniejsza o to. Jak w temacie pisze chodzi mi o problem plecakowy: plecak ma pojemność 12kg. Mam do wyboru przedmioty:
1- o wadze 3 kg i wartości 25,
2- 3kg/wartość- 46
3- 6kg/wartość- 54
4- 6kg/wartość- 89.
I muszę zapakować ten plecak tak, aby miał maksymalną wartość, nie przekraczając pojemności 12kg. Odpowiedź jest prosta- 4 przedmioty o wadze 46kg, ale jak mam to przedstawić za pomocą excela? Proszę o jakąkolwiek pomoc, przewertowałam już wszystko w internecie, ale chyba jestem za mało informatyczna, by zrozumieć wskazówki tam umieszczone. Potrzebuje jakiegoś wytłumaczenia krok po kroku. Z góry dziękuje!
Rozwiązanie dynamiczne:
Tworzysz sobie taką tablicę która dla kolejnych kilogramów (bo mamy tu tylko wartości całkowite) przechowuje maksymalną wartość elementów które można w takiej wadze nieść. Jak je wybrać? Dość łatwo.
dla 0,1,2 kg mamy wartość 0 z powodów oczywistych
Następnie dla 3kg wybieramy sobie najlepszą opcję która się mieści w tym przedziale czyli 46 i teraz zaczyna się prawdziwy algorytm:
dla każdego kolejnego kilograma sprawdzamy sobie dla każdego możliwego przedmiotu czy jeśli cofnęlibyśmy się o tyle kilogramów żeby się ten przedmiot zmieścił to czy element naszej tablicy dla takiej cofniętej wagi + wartość tego przedmiotu nie jest czasem większa od tego co mamy teraz i wybieramy najlepszy przedmiot
0kg 0zł
1kg 0zł
2kg 0zł
3kg 46zł
4kg 46zł
5kg 46zł
6kg 92zł //porównujemy sobie (wartość z tablicy dla 0kg + cena 6 kilogramowej rzeczy),(wartość z tablicy dla 0kg + cena 6 drugiej kilogramowej rzeczy),(wartość z tablicy dla 3kg + cena 3 kilogramowej rzeczy),(wartość z tablicy dla 3kg + cena 3 kilogramowej rzeczy) i wybieramy sobie maksimum, ktore w tym przypadku wynosi 92zł
... itd
Załóżmy jednak na potrzeby edukacyjne że mamy trochę ciekawszy rozkład przedmiotów:
1kg 10zł
3kg 31zł
5kg 100zł
I mamy plecak 8kg
0kg 0zł
1kg 10zł
2kg 20zł
3kg 31zł // teraz porównujemy (0zł+31zł) oraz (20zł + 10zł) i wygrywa 31 [pomijamy rzecz wagi 5kg bo nie możemy nagle wskoczyc na ujemną wagę w plecaku ;)]
4kg 41zł
5kg 100zł //teraz porównujemy (0zł + 100zł), (41zł + 10zł) oraz (20zł + 31zł) i wygrywa 100