Seja
, onde
para todo
. Dados
,
, encontre condições necessárias e suficientes para que:
,
Passo 1
Beleza, bora resumir o que tá rolando. A gente tem um problema tipo “knapsack” (mochila):
- Variáveis binárias
para todo . - Cada item
tem peso (ou “valor”) positivo . - A capacidade da mochila é
.
Então o conjunto de soluções viáveis é
O que a questão pede é: “quais condições necessárias e suficientes sobre
para garantir
Ou seja, sempre que
a gente também devia ter
.
Para resolver isso a gente vai usar:
- Definição de viabilidade no knapsack.
- Observação de que a única forma de violar
é ter .
Passo 2
Vamos entender quando
falha.
Ela falha exatamente se existe algum com
Ela falha exatamente se existe algum
Para esse
, a soma de pesos seria
pois os outros
são 0 ou 1. O menor peso total que dá pra arrumar com
é justamente escolhendo todos os outros
, daí o total fica
.
Passo 3
Agora, quando esse
não pode estar em
?
Se . No caso mínimo que acabamos de falar, isso dá
Se
Em outras palavras, se
, qualquer tentativa de colocar
já estoura a capacidade mesmo que você deixe todo mundo – incluindo
– zerado. Logo não existe vetor em
com
, e então sempre que
você já é obrigado a tomar
(ou senão não tá em
).
Por outro lado, se
, basta escolher o vetor com
para ter
, isto é viável e quebra
.
Resposta
Condição necessária e suficiente: