Programmazione dinamica nell'imballaggio del contenitore

4

Problema: Dato un elenco L di oggetti di dimensioni possibili dal set S = {1,2,4,8} e fornitura illimitata di contenitori di dimensioni 16 ciascuno e dobbiamo usare il minimo possibile numeri di contenitori per imballare tutti gli oggetti di L.
Sto anche cercando una soluzione ottimale (o quasi ottimale) usando la programmazione dinamica o altrimenti nei seguenti scenari quando

  1. L non viene fornito offline, ma ci viene chiesto di adattare gli oggetti uno alla volta senza conoscere le richieste future (imballaggio del contenitore in linea in 1-D).
  2. le dimensioni possono essere da SXS e i contenitori sono di capacità (16,16) ciascuno. (Imballaggio bidone vettoriale).

Presupposto: imballaggio ottimale significa il miglior imballaggio possibile da tutti gli imballaggi possibili, ovvero l'imballaggio con il numero minimo di contenitori utilizzati.
L'imballaggio del contenitore vettoriale effettivamente generalizzato è NP-hard, ma penso che le dimensioni standard dovute da un insieme finito, soluzioni più efficienti e migliori possano esistere.

Il mio approccio: Chiaramente, la modalità offline 1-D può essere compresso in < = optimum + 1 utilizzando l'intelligente associazione di oggetti.
Ma sono bloccato per gli altri 2 aspetti sopra indicati.
Conosco gli algoritmi di First Fit, Best Fit, First Fit Decreasing ma sto cercando questa soluzione specifica per il problema.

    
posta v78 20.07.2014 - 05:20
fonte

1 risposta

1

Per il caso offline 1-Dimensionale, supponiamo di ordinare tutti gli oggetti da grandi a piccoli. A causa delle dimensioni, non si verificheranno tagli netti e tutti i raccoglitori tranne forse l'ultimo verranno riempiti a piena capacità. Immagino che questo sia ciò che intendi con l'intelligente abbinamento.

Per il caso online, se si conservano 4 diversi contenitori, uno per ogni dimensione, allora si sarà in grado di riempire completamente ogni cestino, ad eccezione forse di 4 contenitori. Se l'elenco è abbastanza grande, questo sarà molto vicino a una soluzione ottimale. Le dimensioni dell'elenco L e la probabilità di ciascuna dimensione si verificano in anticipo?

    
risposta data 30.08.2016 - 21:23
fonte

Leggi altre domande sui tag