Problem plecakowy, związek ze doborem świadłowodów

Question

Dzień dobry,
piszę projekt na algorytmy i struktury danych i natrafiłem na pewien problem. Otóż muszę wykorzystać zagadnienie dynamicznego programowania w problemie plecakowym do doboru optymalnego zestawu światłowodów. Sytuacja wygląda tak, że mam graf i muszę wybrać ścieżkę między centralą a klientami tak aby było najtaniej. Tutaj pojawia się zagadnienie doboru światłowodów.
Weźmy sytuacje, że mam kable z światłowodami takie, że:
3 włókna światłowodu w kablu za 5 zl/m
5 włókien za 7zł/m
8 włókien za 8zł/m
Polega to na doborze kabli tak aby wyszło najtaniej i wszyscy klienci byli podpięci do sieci czyli zrobieniu tabelki taką jak w problemie plecakowym (czyli taką, że pokazuje dla jakiej wagi plecaka jaką największą wartość można władować do niego) tylko taką, która pokazuje, że dla danej ilości klientów koszt za metr jest taki.
Nie potrafię powiązać problemu plecakowego ze znajdowaniem najmniejszego kosztu. Przecież w problemie plecakowym szukamy największego kosztu a nie najmniejszego dla danego ciężaru (czyli w tym przypadku danej ilości klientów).
Jeśli ktoś nie będzie czegoś rozumiał to proszę o komentarz a postaram się doprecyzować.
Dzięki

Answer 1

Musisz lecieć po 1 wierzchołku i obliczać jaką wiązkę dać i do kogo