[Medved]

#algorytmy #kiciochpyta #programowanie
Czy potrafi ktoś najprościej opisać algorytm w zagadnieniu wieloplecakowym? #pdk Póki co, obliczam stosunek każdego z trzech pramatrów (cena/waga/objętość), sortuję je od największego i upycham do plecaków póki nie skończy się objętość lub waga plecaka (sprawdzam w miedzyczasie czy obiekt może byc też opd tym względem włożony). Problem w tym że nie wiem w jaki sposób algorytm ma wiedzieć kiedy wyjąć jakiś przedmiot aby włożyć do niego inny dzięki któremu lepiej zapcham dany plecak.

[segfault]

@Medved: Wieloplecakowym? Nie udało mi się wygooglać tego określenia. Mógłbyś opisać na czym polega ten problem?

[Medved]

@segfault: standardowy problem plecakowy polega na tym aby dane przedmioty, mające dwa parametry(np. cenę oraz wagę) tak umieścić w plecaku (posiada tylko ciężar ) aby były ułożone jak najbardziej optymalnie i maksymalnie do końca. W skrócie, wsadzić do plecaka tyle ile się da z jak największą wartością wszystkich przedmiotów. W wieloplecakowym jest po prostu n-plecaków. Reszta jest w pytaniu wyżej

[danielet]

@Medved: polecam zrobić dodatkowa zmienna ktora bedzie oznaczała proporcje cena:waga. Im większa ta liczba - proporcja tym lepiej

[Medved]

@danielet: to już mam, problem w tym, że nie wiem, dzięki jakiemu parametrowi czy funkcji, algorytm, ma wyciągnąć dany przedmiot aby umieścić lepszy np z końca listy. Np. Podczas wypełnienia plecaka zostało 0.3 kg miejsca, a cena całości to np 20. Musimy wyjąć ostatni przedmiot który zajmuje np 0.7 i ma wartość 3 i wrzucić przedmiot, który zajmuje 1 wagi i 5 wartości. Dla jednego plecaka to po prostu wrzucanie przedmiotów