Algoritma tasarımı: Çoklu sırt çantası problemine bir çözüm sunabilir misiniz? Ben etkili olanlarla sözde kod çözüm arıyorum

Question

Multiple Knapsack Problem (optimizasyon deyimi sayfa aşağı yarıya ise). Ben çözüm bulmak çok verimli ve kolay iyi olacağını hayata ziyade eğer optimum olması gerekmez böylece bu sorun NP Complete olduğunu düşünüyorum . Her zaman tamamlamak için farklı (ancak sabit ve bilinen) tutarını alarak, birçok iş çizelgesine

• :

  sorun budur.

• Ben (ideal) grupların en küçük numarasına sahip şekilde çalışma öğelerinin her grup belirli bir toplam eşikten artık alarak, gruplar halinde bu çalışma öğeleri bölmek gerekir - 1 saat söylüyorlar.

Eşik konusunda esnekim - sıkı bir şekilde uygulanmasına gerek yok, ancak yakın olmalıdır. Fikrim, iş öğelerini her bir bölmenin eşiğin% 90'ını,% 80'ini,% 70'ini temsil ettiği çöp kutularına ayırmaktı. Daha sonra% 90 alanlara% 90 oranında sahip olan eşyaları eşleştirebilirim.

Daha iyi bir fikir?

Answer 1

Sen bölüm 6.6 "- Yaklaşık algoritmalar Çoklu knapscack sorunu", http://www.or.deis.unibo.it/knapsack.html gerekir. Metin ve Fortran uygulamalarında sözde kod (Pascal stili) var (evet, eski bir kitap) bir ZIP dosyası olarak.

Answer 2

Bildiğim kadarıyla, sorun NP tamamlandı (Wikipedia confirms), bu yüzden tam olarak çözmeyi denemede pek bir anlam ifade etmiyor. Ancak yaklaşımların herhangi bir sayıda sizin için yeterince iyi olabilir:, açgözlü, genetik algoritmalar benzetilmiş tavlama ... açgözlü muhtemelen uygulamak için en kolay:

while (time available in block greater than smallest task duration) 
    find the longest fitting task 
    add it 

... anladınız.