Prova di un avido algoritmo utilizzato per una variazione del problema del bin-imballaggio

Question

ci viene data una serie di pesi $ W $ (tutti i pesi sono numeri interi positivi), e dobbiamo mettere il pesi all'interno dei bidoni.Ogni bin può contenere un massimo di max_val, e ogni peso è al massimo max_val.La variazione è che l'ordine dei pesi non deve essere modificato, cioè, $ w_i $ dovrebbe essere all'interno di un cestino prima di $W_j $ è inserito, per tutti $ i .

Per questa dichiarazione del problema, intuitivamente possiamo vedere che un avido approccio di riempire un cestino fino a raggiungere il suo valore massimo viene raggiunto e creare un nuovo cestino per ulteriori pesi produrrà il numero minimo di contenitori.Non riesco a trovare una prova formale che la soluzione avida è ottimale.Qualsiasi suggerimento o linee guida sarebbe fantastico!

Answer 1

Let $ G $ Sii la soluzione prodotta dall'algoritmo avido. Per l'altra soluzione $ s $ , Let $ I (s) $ Sii l'indice del primo peso A quale $ s $ diverge da $ G $ . Let $ o $ Sii una soluzione ottimale massimizzando $ i (o) $ . Quindi $ G $ Posizioni $ i (o) $ in bin $ J $ (per alcuni $ J $ ) e $ o $ Posizioni < Span Class="Math-Container"> $ i (o) $ in bin $ j + 1 $ . Se spostiamo $ i (o) $ per bin $ J $ (che è possibile da $ o $ è ordinato), otteniamo una soluzione $ o '$ usando al massimo il maggior numero di contenitori come $ o $ e soddisfacente $ i (o ')> I (o) $ . Questo contraddice la scelta di $ o $ .

Se proviamo a gestire questo argomento sull'algoritmo di imballaggio del cestino senza restrizioni, avremo problemi quando si spostano $ i (o) $ a bin $ J $ , poiché quel cestino potrebbe essere occupato con altri elementi, non lasciando abbastanza spazio per $ i (o) $ . Nella variante si considera, questo non può accadere.