- A preencher
- Lida
- Resposta
Problema da mochila
Só consegue carregar um certo peso, e cada item tem um peso e um valor. Que itens leva para carregar o maior valor? Experimentar todas as combinações duplica o trabalho a cada item. Uma tabela com uma linha por item e uma coluna por capacidade encontra a melhor mochila, uma célula de cada vez. Toque num item para o meter na mochila e toque nele outra vez (na mochila ou na prateleira) para o tirar. A mochila enche-se pelo peso, e os quadros mostram os dólares que meteu na mochila face ao melhor possível. Prima Melhor arrumação para ver a melhor mochila. No painel, altere os quilos e os dólares dos itens, adicione ou remova itens e defina a capacidade da mochila. A vista Tabela mostra como a programação dinâmica encontra a melhor mochila: prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez, e arraste o controlo de passos para saltar para qualquer ponto. Cada linha acrescenta um item, cada coluna é uma capacidade em quilos e cada célula guarda o máximo de dólares que cabe. Com a tabela selecionada, as teclas de seta avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e para o fim.
Como funciona
- Toque nas caixas para as pôr na mochila e veja-a encher-se pelo peso em quilos.
- Tente chegar ao melhor valor possível em dólares, ou prima Melhor arrumação para ver a melhor mochila.
- Abra a vista Tabela e prima Reproduzir para ver cada célula escolher entre levar e deixar um item.
Como funciona a tabela
Cada linha acrescenta um item e cada coluna é uma capacidade, de 0 até à da mochila. Uma célula guarda o maior valor que cabe nessa capacidade usando os itens até à sua linha. Sem o novo item, é a célula de cima. Com ele, se couber, é o valor do item mais o melhor valor para o peso que sobra, que está na linha de cima, tantas colunas à esquerda quanto o peso do item. A célula fica com o maior dos dois. A primeira linha, sem itens, é toda de zeros.
Reconstruir os itens
A célula do canto inferior direito é o melhor valor. Para encontrar os itens, comece aí e compare-a com a célula de cima: se for igual, o último item não era necessário; se for maior, o item está na mochila, por isso subtraia o seu peso e passe para essa coluna. Suba uma linha de cada vez até à primeira. A aplicação mostra esta reconstrução a laranja e lista os itens na mochila por baixo da tabela.
Perguntas frequentes
O que significa 0/1 no problema da mochila 0/1?
Cada item é levado uma vez ou nenhuma, nunca em parte e nunca duas vezes. Se os itens pudessem ser cortados, como grãos de arroz, levar primeiro o melhor valor por peso seria ótimo; esse é o problema da mochila fracionária.
Porque não levar primeiro o melhor valor por peso?
Porque os itens inteiros podem deixar espaços vazios. Com uma capacidade de 7 e itens de peso 1, 3, 4 e 5 que valem 1, 4, 5 e 7, o melhor valor por peso é o do item de peso 5, que só deixa espaço para o item de peso 1, num total de 8. Os itens de peso 3 e 4 juntos valem 9.
Quão rápido é o algoritmo da mochila?
A tabela tem (número de itens + 1) vezes (capacidade + 1) células, cada uma preenchida num passo. Isso é rápido para capacidades pequenas, mas uma capacidade pode ser um número enorme, por isso o problema é NP-difícil em geral; o método da tabela diz-se pseudopolinomial.
O mesmo item pode ser metido duas vezes?
Aqui não. No problema da mochila ilimitada, cada item pode ser levado qualquer número de vezes; a tabela lê então a célula à esquerda na mesma linha em vez da linha de cima, como na aplicação do troco.
É enviado algo para algum lado?
Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor