Mam takie zadanie:
Dyskretny problem plecakowy:
a) rozwiąż problem plecakowy, korzystając z metody "dziel i zwyciężaj".
b) rozwiąż problem plecakowy, korzystając z programowania dynamicznego.
Za nic nie czaję, jak można tu wykorzystać te dwie metody, do problemu plecakowego.
Rozumiem, że trzeba wybierać, najlepszą opcję. Powiedzmy, że mamy 6-cio kg plecak i takie dane:
3 - 3kg
3 - 3kg
6 - 4kg
1 - 3kg
Jakbym mial stworzyć algorytm który miałby wybrać najlepszą opcję, to prawdopodobnie sprawdzałbym procentowo wartość w stosunku do wagi i od pojemnosci plecaka odejmowalbym wagę, bo tutaj w tym przykladzie byłoby najlepszą opcją wziąć 6 - 4kg (150% i 2kg puste) lub 3 - 3kg i 3 - 3kg (100% i 100% i 0 kg puste).
Chociaż z drugiej strony, gdyby były takie dane:
3 - 3kg
3 - 3kg
6 - 4kg
1 - 2kg
to lepsza opcja byloby wziąć 6 - 4kg i 1 - 2kg (150% i 50% i 0 kg puste). Nie wiem jak algorytm przedstawić. Proszę o pomoc.