Problem plecakowy: Różnice pomiędzy wersjami

Dodane 16 bajtów ,  1 rok temu
Znacznik: edytor kodu źródłowego 2017
Znacznik: edytor kodu źródłowego 2017
Problem plecakowy może być rozwiązany w [[algorytm pseudowielomianowy|czasie pseudowielomianowym]] przy użyciu [[programowanie dynamiczne|programowania dynamicznego]]. Rozwiązanie niżej dotyczy przypadku w którym można użyć wielokrotnie każdego elementu:
 
Niech <math>w_1, \dots, w_n</math> będą wagami poszczególnych elementów oraz <math>c_1, \dots, c_n</math> ich wartościami. Algorytm ma zmaksymalizować sumę wartości elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej <math>W.</math> Niech <math>A(i)</math> będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej <math>i.</math> <math>A(W)</math> jest rozwiązaniem problemu.
 
<math>A(i)</math> jest zdefiniowane rekurencyjnie:
14 227

edycji