O conjunto é fornecido. Para cada elemento , temos peso e custo . O objetivo é encontrar o subconjunto de tamanho que maximize a seguinte função objetivo: .
O problema é NP-difícil?
Como a função objetivo parece estranha, é útil explicar uma aplicação da função objetivo.
Suponha que tenhamos n itens a e que haja cópias de cada objeto em nosso inventário. Temos alguns clientes e eles estão interessados nesses objetos na proporção do seu peso , o que significa que o objeto com maior é mais popular. Temos um sistema de venda on-line e precisamos responder às solicitações de nossos clientes corretamente. Não podemos reconhecer objetos por suas formas (todos parecem iguais!). Mas temos algum classificador para encontrá-los. Cada classificador pode ser usado para detectar cópias de um objeto. Nosso objetivo é executar o classificador k, a fim de maximizar a satisfação de nossos clientes.
PS: Pode ser útil pensar no caso em que para todos os ; no entanto, não tenho certeza. [ Eu estava errado sobre isso! Está em P por esta suposição ]
fonte
Respostas:
A resposta abaixo observa que um caso especial do problema é solucionável em tempo polinomial. Isso não responde totalmente à pergunta no post, mas pode fornecer algumas dicas sobre o que pode ser necessário para uma prova de dureza NP e provocar um interesse adicional no post ...
Observação. O problema no post tem um algoritmo que, dada qualquer instância em que cada é um número inteiro, é executado no polinômio do tempo em e . n D = Σ i c ici n D=∑ici
Esboço de prova. Corrija qualquer entrada que e (WLOG) . Reformulando um pouco o problema, o objetivo é encontrar de tamanho maximizando .w , c ∈ R n + S = { 1 , 2 , … , n } M ⊆ S K ∑ i ∈ M w i c i(S,w,c,K) w,c∈Rn+ S={1,2,…,n} M⊆S K ∑i∈Mwici∑i∈Mci−∑i∈Mwi
Considere o seguinte programa dinâmico. Para quaisquer números inteiros com , e , defina A solução desejada é .(d1,d2,k,m) 0≤d1≤d2≤D 0≤k≤K k≤m≤n
Particionando as possíveis soluções para naquelas que contêm e naquelas que não contêm , obtemos a recorrência Deixamos os casos de fronteira como um exercício.ϕ(d1,d2,k,m) m
O número de sub-problemas é , e para cada lado da mão direita da recorrência pode ser avaliada em tempo constante, de modo que o algoritmo é executado em tempo polinomial em e .O(n2D2) n D □
Corolário. A menos que P = NP, qualquer redução que mostre a dureza NP será reduzida para instâncias em que não é polinomial em .D n
Observação. A menos que eu esteja enganado, também há um PTAS para o problema no post, com base no arredondamento dos 's e usando programação dinâmica. No entanto, a existência de um PTAS não tem relação direta com a dificuldade do NP, conforme solicitado no post.wi
Também estou curioso --- alguém sabe se o caso especial quando (para cada ) tem um algoritmo de poli-tempo? (EDIT: sim, pelo comentário de Willard Zhan, isso parece ser otimizado ao usar para conter os maiores elementos.)wi=ci i M k
fonte
Você está perguntando sobre a maximização de uma função sem restrições?
É realmente simples. Se M é o maior conjunto, então é a melhor solução. Não há necessidade de calcular nada.
Esse problema parece semelhante ao problema da mochila, que é NP por sinal.
fonte