C++ problem plecakowy dyskretny


(Stan19) #1

Witam.

Mam problem ze znalezieniem przedmiotów które wchodzą do zbioru przedmiotów o sumie największej wagi.

Korzystam z algorytmów

38167539353088156638_thumb.jpg

89706888090053964017_thumb.jpg

w programie mam #define I i-1

Oto mój kod:

Dla pewnych sytuacji kod wypisuje mi wagę większą niż dopuszczalna (bierze dodatkowe przedmioty do liczenia sumarycznej wagi) lecz maksymalna wartość jest zawsze dobra. 

 

 


(kostek135) #2

Twoja metoda wyszukiwania, co włożyliśmy do plecaka, to bzdura. Nie możesz sobie tego oznaczać w else, bo nie bierzesz pod uwagę, że jakiś przedmiot mógł zostać zapakowany kosztem innego. Stąd jeśli masz taki zbiór przedmiotów, który spowoduje, że jeden przedmiot wypchnie drugi, to masz problem. Zrób to metodą backtracking-u na policzonej tablicy: