Hogyan lehet megoldani a csomagolás problémáját konténerekben (egydimenziós)

  • C ++
  • Feladatok kezelése
  • algoritmusok

Jó napot.
A különböző dimenziók N méretű elemeinek különböző dimenziójú M tartályokban való elosztásával kapcsolatos feladatok. Az egész állapotot így fogalmazták meg:

Bevitelként:
M - konténerek száma, A1 számjegyek M. A, ami megfelel a tartályok kapacitásának (az elemekben).
N - elemek száma, N számok B1. Bn, ezeknek az elemeknek a méreteit.

A feladat az, hogy az elemek optimális eloszlását adja meg a tartályok mentén ebben a változatban:
Output N számok, ahol a j-os számnak meg kell jelölnie a konténer számát, amelybe a j-es elemet helyezzük.

Például:
4 tartály, kapacitás
11 7 4 3
5 elem, méret
6 3 2 4 5

Következtetés (az egyik lehetséges):
1 2 4 2 1

Sajnos az algoritmikus és az NP-problémák nem erősek, és eddig ötleteire ebben a témában nem sok. Gondoltam arra, hogy a nagyobb méretűtől a kisebb és könnyebb válogatásig válogattam a töltelékkel - pl. Próbálj ki minél többet a legnagyobb tartály, a második, stb. Használatához. de ebben az esetben a kezdeti indexálás (sorrend) megőrzésének problémája van.

Mondja meg nekem, kérlek, vagy cikkeket olvasni e témában, vagy egy megfelelő algoritmust. Köszönjük előre.)

Kapcsolódó cikkek