optymalizacja - minimalna liczba koszy

Question

Cześć,

proszę o pomoc w znalezieniu algorytmu, który pozwoli mi rozwiązać następujące zadanie: 

Mamy zbiór A zawierający rożnego rodzaju klocków ( o rozmiarach od 1.0 do 10.0 - 'kwant' to 0.1). Mam również kosze, których pojemność wynosi 10. Zadanie polega na tym, aby umieścić wszystkie klocki w jak najmniejszej ilości koszów.

Przykładowe dane:
A = [1.3, 2.9, 2.8, 4.5, 6.9, 10.0]

Na ten moment mam algorytm, który po kolei sprawdza liczby w zbierze A i sprawdza ich sumy. W ten sposób otrzymuję 4 koszy: [1.3, 2.9, 2.8] [4.5] [6.9] [10.0].

Nie jest to optymalne rozwiązania, lepszym jest chociażby: [10.0] [6.9, 2.9] [1.3, 4.5, 2.8].

Czy mógłbym Was prosić o pomoc w opracowaniu jakiegoś algorytmu?

 

Answer 1

https://pl.wikipedia.org/wiki/Problem_plecakowy

Comments

To nie jest przypadkiem problem NP-trudny? Wtedy plecak mało zdziała

---

To rozwiązuje mój problem.

Rozwiązuję ten problem dla zadanego zbioru w następujący sposób:

-  obliczam skład pierwszego kosza na podstawie zbioru [1.3, 2.9, 2.8, 4.5, 6.9, 10.0]: 1.3;2.9;2.8;4.5 (suma 11.5) -> mamy 1 kosz

-  obliczam skład drugiego kosza na podstawie zbioru [6.9, 10.0]: 6.9 (suma 6.9) -> mamy 2 kosz

-  obliczam skład drugiego kosza na podstawie zbioru [10.0]: 10.0 (suma 10.0) -> mamy 3 kosz

---

Jak dokładnie obliczasz skład każdego kosza? Korzystasz z tego plecaka?

---

Tak, mój skrypt bazuje na podstawie tego rozwiązania: http://rosettacode.org/wiki/Knapsack_problem/0-1#PHP

Wykonuję ten algorytm na zbiorze pomniejszonym o już użyte elementy. Nie jest to może najwydajniejszy sposób, ale dla mnie wystarczający.