Problema da mochila com restrição de número de item exigido exigido

Question

Como resolveríamos o problema da mochila se agora tivermos que corrigir o número de itens na mochila por uma constante $ l $ ?Este é o mesmo problema (peso máximo de $ W $ , cada item tem um valor $ v $ epeso $ W $ ), mas você deve adicionar exatamente $ l $ Item(s) para a mochila (e obviamente precisa otimizar o valor total da mochila).

Todas as meios que eu pensei em implementar isso até agora (programação dinâmica, força bruta) resultou em falhas, ou tempos de computação no nível da vida do universo.Qualquer ajuda ou ideias é apreciada.

editar: Estou à procura de soluções de tempo pseudo-polynomial

Answer 1

Você pode transformar esse problema em uma instância de mochila. Deixe $ n $ Seja o número de itens, $ v $ Seja o valor máximo de um item e suponha que cada item pesa no máximo $ W $ (caso contrário, pode ser descartado).

Para garantir que você selecione pelo menos $ l $ Itens:

• add $ n (v + 1) $ para o valor de cada item.
• Agora, o problema é equivalente ao de maximizar o número de itens selecionados, quebrando os laços em favor do conjunto de itens com maior valor total original, sujeito a restrições de peso. Há uma solução que seleciona pelo menos $ l $ Itens IFF A solução ideal tem um valor de pelo menos $ n (v +1) L $ .

Para garantir que você selecione no máximo $ l $ itens:

• adicionar $ (W + 1) $ para o peso de cada item.
• add $ l (w + 1) $ para $ W $ .
• agora cada subconjunto de mais de $ l $ itens pesa pelo menos $ (L + 1) (W + 1 )= L (W + 1) + (W + 1)> L (W + 1) + W $ e é, portanto, não viável. Cada subconjuo de $ l $ itens que tinham um peso total de $ W $ , agora pesa $ l (W + 1) + W $ e, portanto, é viável IFF $ w \ le W $ . Um subconjunto com menos de $ l $ itens podem ser viáveis, mesmo que seu peso geral seja mais do que $ W $ , no entanto, seu valor total será sempre menor do que $ n (v + 1) l $ .