Autor Wątek: Problem plecakowy - programowanie dynamiczne  (Przeczytany 1155 razy)

Offline Trix

  • Użytkownik

# Listopad 09, 2014, 01:43:15
Dwa (w zasadzie 3) pytanka dot. programowania dynamicznego dla problemu plecakowego:

1.Mam daną tabelkę:

Wi - wartość i'tego przedmiotu
Oi - objętość i'tego przedmiotu

                                                  Objętość
Wi   Oi               0     |    1     |    2     |    3    |     4     |    5
____________________________________________________
-      -             0  0     |    0          0          0          0          0
35   1            1  0     |    35        35        35        35        35
65   6            2  0     |    35        35        35        35        35
40   3            3  0     |    35        35        40        75        75
50   2            4  0     |    35        50        85        85         x

1. Dobrze jest ona uzupełniona?
2. Co wstawić za x? Wartość 90? czy 85?
3. W miejscu x algorytm co dokładnie sprawdza?
    a) czy wartość 50 > (4, 5) = 75
    b) potem czy przedmiot nr. 4 i nr 1 zmieszczą się do plecaka
    c) i ostatecznie przedmiot nr. 4 i nr. 3 zmieszczą się do plecaka
?

Robię prezentacje, a mój wykładowca wypytuje się szczegółów, także muszę to zrozumieć oraz zaprogramować przykładowy program.
« Ostatnia zmiana: Listopad 09, 2014, 01:45:17 wysłana przez Trix »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych