Suponha que, em um problema de mochila 0-1, a ordem dos itens ordenados por peso crescente seja igual à sua ordem quando eles são ordenados por valor decrescente. Forneça um algoritmo eficiente com o objetivo de encontrar uma solução ótima para essa variante do problema da mochila e mostre que seu algoritmo é correto.
Solução:
A seguir, encontra-se o pseudocódigo para o algoritmo que resolve o problema alterado da mochila:
Var-0-1-Knapsack(v, w, n, W)
1 sw ← sv ← 0
2 i ← 1
3 while (i ≤ n) and ( sw + wi ≤ W )
4 sw ← sw + wi
5 sv ← sv + vi
6 i ← i + 1
7 return sw, sv, i
O algoritmo proposto sempre escolhe o elemento restante de menor peso, pois ele tem ao mesmo tempo o menor peso e o maior valor dentre os elementos restantes.
Para provar a correção do algoritmo, podemos considerar o seguinte:
Existe uma mochila S produzida pelo algoritmo que é uma solução ótima para o problema apresentado. Suponha que exista uma solução S' melhor que S. A solução S' deve conter pelo menos um elemento ei que não existe na solução S. No entanto, o algoritmo sempre escolhe a cada etapa o elemento de menor peso e maior valor dentre os ainda não escolhidos. Logo, qualquer troca de elemento resultará na inclusão de um elemento de maior peso (ou pelo menos igual) e/ou de menor valor (ou pelo menos igual) aos elementos que compõem a solução S, pois esta inclui os k elementos mais leves e ao mesmo tempo mais valiosos. Logo, a proposição da existência de uma solução melhor que S é absurda.