Problema di zaino con esatto vincolo del numero dell'articolo richiesto

Question

Come risolveremmo il problema dello zaino Se ora dobbiamo risolvere il numero di elementi nell 'zaino da una costante $ l $ ?Questo è lo stesso problema (peso massimo di $ W $ , ogni articolo ha un valore $ V $ ePeso $ w $ ), ma è necessario aggiungere esattamente $ l $ Articolo(s) al raccoglitore (e ovviamente è necessario ottimizzare il valore totale dell 'zaino).

Ogni modo di aver pensato di implementarti finora (programmazione dinamica, forza bruta) ha portato a un fallimento o ai tempi di calcolo del livello di livello di vita.Qualsiasi aiuto o idee sono apprezzati.

Modifica: Sto cercando soluzioni temporali Pseudo-polinomiale

Answer 1

Puoi trasformare questo problema in un'istanza di zaino. Let $ N $ Sii il numero di elementi, $ v $ essere il valore massimo di un oggetto e supponiamo che ogni articolo pesa al massimo $ W $ (altrimenti può essere scartato).

Per assicurarti di selezionare almeno $ l $ Articoli:

.
• Aggiungi $ N (V + 1) $ al valore di ogni elemento.
• Ora il problema è equivalente a quello di massimizzare il numero di elementi selezionati, rompere i legami a favore dell'insieme di elementi con il più grande valore totale originale, soggetto a vincoli di peso. C'è una soluzione che seleziona almeno $ l $ Articoli IF La soluzione ottimale ha un valore di almeno $ N (V +1) l $ .

Per assicurarti di selezionare al massimo $ L $ Articoli:

.
• Aggiungi $ (w + 1) $ al peso di ogni oggetto.
• Aggiungi $ l (w + 1) $ a $ w $ .
• Ora ogni sottoinsieme di più di $ l $ gli articoli pesa almeno $ (l + 1) (w + 1 )= L (w + 1) + (w + 1)> l (w + 1) + w $ , ed è quindi non fattibile. Ogni sottoinsieme di $ l $ elementi che avevano un peso complessivo di $ W $ , ora pesa $ L (w + 1) + w $ , e quindi è fattibile IFF $ w \ le w $ . Un sottoinsieme con meno di $ l $ gli articoli potrebbero essere fattibili anche se il suo peso complessivo è più di $ W $ , tuttavia il suo valore totale sarà sempre più piccolo di $ N (V + 1) L $ .