Rozszerzony Problem Plecakowy - n plecaków o pojemności m

Witam,

czy ktoś z Was wie może, jak nazywa się algorytm, który pozwoli rozwiązać następujący problem:

mamy n plecaków, każdy o objętości m i k pakunków każdy o objętości od o[1] do o[k]...

Trzeba je upakować w taki sposób, aby zająć jak największą część dostępnej powierzchni, wynikiem ma być zajęta przestrzeń (liczba z przedziału 0 do m x n)

Proszę o pomoc...

To mi wyglada na typowe zadanie z olimpiady informatycznej. Jezeli tak jest to nieznajdziesz tutaj pomocy, a wiesz dlaczego ? Bo zadania z OI trzeba robic samodzielnie :>

mnie to wygląda na zwyczajny problem plecakowy

Ani jedno ani drugie, zadanie jest z informatyki w gimnazjum ;/
Zwykły problem plecakowy opiera się na jednym "kontenerze"

Pozdrawiam i proszę o pomoc

Zwykły problem plecakowy jest NP-trudny, ten rozszerzony problem na oko też wpada do tej klasy. Czyli algorytmu znajdującego optymalne rozwiązanie w rozsądnym czasie raczej nie znajdziesz (chyba, że jesteś geniuszem i obalisz wielce prawdopodobną hipotezę, że P != NP).
Możesz tylko kombinować z heurystykami. Podam jedną z najprostszych (zachłanną, dosyć naiwną):

1. Sortujesz wszystkie rzeczy wg malejącej wartości.
2. Sortujesz wszystkie plecaki wg malejącej wielkości.
   3 Bierzesz pierwszy plecak i pierwszą rzecz.
3. Jeśli jest miejsce umieszczasz tam rzecz.
4. Jeśli nie ma miejsca i jest kolejny plecak, bierzesz kolejny plecak i skok do 4.
5. Jeśli nie ma miejsca i to już ostatni plecak, bierzesz kolejną rzecz i skok do 4.
6. Jeśli nie ma miejsca i nie ma więcej plecaków i nie ma więcej kolejnych rzeczy -> skok do 3.
7. Jeśli w procesie 3-6 nie została dodana żadna rzecz do żadnego plecaka -> koniec.

Mam nadzieję, że to trochę pomoże.