O problema da mochila ilimitada, também conhecido como problema da mochila não restrita, é um clássico problema de otimização. Dada uma capacidade de mochila e um conjunto de itens, cada um com um peso e valor, o objetivo é maximizar o valor total dos itens que podem ser colocados na mochila. A característica distintiva deste problema é que cada tipo de item está disponível em quantidade infinita.
Existem duas variações principais deste problema:
- Encontrar o valor máximo que pode ser obtido sem exceder a capacidade da mochila.
- Encontrar o valor máximo que pode ser obtido quando a mochila é preenchida exatamente até a sua capacidade.
Abordagem de Programação Dinâmica
A programação dinâmica é uma técnica poderosa para resolver problemas de otimização que podem ser decompostos em subproblemas sobrepostos. Para o problema da mochila ilimitada, definimos um estado e uma relação de transição para construir a solução.
Questão 1: Valor Máximo (Capacidade Flexível)
Representação do Estado:
Seja dp[j] o valor máximo que pode ser obtido com uma mochila de capacidade j.
Relação de Transição:
Para calcular dp[j], consideramos cada item i com peso v[i] e valor w[i]. Se o peso atual j for maior ou igual ao peso do item i (j >= v[i]), podemos potencialmente incluir este item. Se incluirmos o item i, o valor total será o valor do item w[i] mais o valor máximo que pode ser obtido com a capacidade restante j - v[i], que é dp[j - v[i]]. Como podemos usar múltiplos de cada item, a relação de transição se torna:
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) para todos os itens i tais que j >= v[i].
Inicialização:
dp[0] = 0 (nenhum item pode ser colocado em uma mochila de capacidade 0, resultando em valor 0).
Ordem de Preenchimento:
Iteramos sobre a capacidade da mochila de 1 até V. Para cada capacidade j, iteramos sobre todos os itens disponíveis.
Resultado:
O resultado para a primeira pergunta é dp[V].
Questão 2: Valor Máximo (Capacidade Exata)
Representação do Estado:
Seja dp[j] o valor máximo que pode ser obtido com uma mochila de capacidade exatamente j. Se uma capacidade j não puder ser atingida, representamos com um valor especial, como -1.
Relação de Transição:
A relação de transição é semelhante à anterior, mas com uma verificação adicional:
dp[j] = max(dp[j], dp[j - v[i]] + w[i]) para todos os itens i tais que j >= v[i] e dp[j - v[i]] != -1 (garantindo que a subcapacidade é alcançável).
Inicialização:
dp[0] = 0. Todas as outras entradas dp[j] para j > 0 são inicializadas com -1 para indicar que ainda não são alcançáveis.
Ordem de Preenchimento:
Semelhante à primeira questão, iteramos sobre a capacidade da mochila de 1 até V. Para cada capacidade j, iteramos sobre todos os itens disponíveis.
Resultado:
O resultado para a segunda pergunta é dp[V]. Se dp[V] for -1, significa que a capacidade exata não pode ser alcançada, e retornamos 0.
Otimização do Espaço
Observamos que, na relação de transição dp[j] = max(dp[j], dp[j - v[i]] + w[i]), o cálculo de dp[j] depende apenas de valores de dp com índices menores ou iguais a j. Isso nos permite otimizar o uso do espaço, utilizando um único array dp de tamanho V + 1.
A ordem de iteração para a capacidade j deve ser da esquerda para a direita (de 1 a V) para garantir que estamos usando os valores do estado anterior (ou seja, usando a lógica do problema da mochila ilimitada onde múltiplos do mesmo item podem ser usados).
Exemplo de Implementação (Java)
import java.util.Scanner;
public class FullKnapsack {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // Número de itens
int capacity = scanner.nextInt(); // Capacidade da mochila
int[] weights = new int[n];
int[] values = new int[n];
for (int i = 0; i < n; i++) {
weights[i] = scanner.nextInt();
values[i] = scanner.nextInt();
}
// Questão 1: Valor máximo (capacidade flexível)
int[] dpMaxVal = new int[capacity + 1];
for (int j = 1; j <= capacity; j++) {
for (int i = 0; i < n; i++) {
if (j >= weights[i]) {
dpMaxVal[j] = Math.max(dpMaxVal[j], dpMaxVal[j - weights[i]] + values[i]);
}
}
}
System.out.println(dpMaxVal[capacity]);
// Questão 2: Valor máximo (capacidade exata)
int[] dpExactVal = new int[capacity + 1];
for (int j = 1; j <= capacity; j++) {
dpExactVal[j] = -1; // Inicializa com -1 para indicar não alcançável
}
dpExactVal[0] = 0; // Capacidade 0 é alcançável com valor 0
for (int j = 1; j <= capacity; j++) {
for (int i = 0; i < n; i++) {
if (j >= weights[i] && dpExactVal[j - weights[i]] != -1) {
dpExactVal[j] = Math.max(dpExactVal[j], dpExactVal[j - weights[i]] + values[i]);
}
}
}
if (dpExactVal[capacity] == -1) {
System.out.println(0);
} else {
System.out.println(dpExactVal[capacity]);
}
scanner.close();
}
}
Problema Semelhante: Troco de Moedas
O problema da "Troco de Moedas" (Coin Change) é uma variação direta do problema da mochila ilimitada, onde o "valor" de cada item é 1 (representando uma moeda), e o objeitvo é encontrar o número mínimo de moedas para formar uma determinada quantia (a "capacidade").
Troco de Moedas (Número Mínimo de Moedas)
Representação do Estado:
Seja dp[j] o número mínimo de moedas necessárias para formar a quantia j.
Relação de Transição:
dp[j] = min(dp[j], dp[j - coin_value] + 1) para cada valor de moeda coin_value tal que j >= coin_value.
Inicialização:
dp[0] = 0. Todas as outras entradas são inicializadas com um valor infinito (representando não alcançável), como Integer.MAX_VALUE ou um valor grande como 0x3f3f3f3f.
Resultado:
dp[amount]. Se o resultado for infinito, retorna -1.
Troco de Moedas II (Número de Combinações)
Representação do Estado:
Seja dp[j] o número de combinações únicas de moedas que somam a quantia j.
Relação de Transição:
dp[j] = dp[j] + dp[j - coin_value] para cada valor de moeda coin_value.
Inicialização:
dp[0] = 1 (há uma maneira de formar a quantia 0: não usar nenhuma moeda). Todas as outras entradas são inicializadas com 0.
Ordem de Preenchimento (Importante):
Para contar combinações únicas, a ordem de iteração é crucial. Iteramos primeiro sobre as moedas e, em seguida, sobre a quantia. Isso garante que cada combinação seja contada apenas uma vez.
class CoinChangeII {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1; // Uma maneira de fazer 0 é não usar moedas
// Iterar primeiro sobre as moedas para contar combinações únicas
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
}
Problema Relacionado: Números Quadrados Perfeitos
Este problema pode ser visto como um caso especial do problema da mochila ilimitada, onde os "itens" são os números quadrados perfeitos (1, 4, 9, 16, ...), e o "valor" de cada item é 1. O objetivo é encontrar o número mínimo de "itens" (números quadrados perfeitos) que somam a "capacidade" n.
Representação do Estado:
Seja dp[i] o número mínimo de quadrados perfeitos que somam i.
Relação de Transição:
dp[i] = min(dp[i], dp[i - j*j] + 1), onde j*j é um quadrado perfeito menor ou igual a i.
Inicialização:
dp[0] = 0. Pode-se inicializar dp[i] com um valor grande (como i, pois o pior caso é usar i vezes o número 1).
Resultado:
dp[n].
class PerfectSquares {
public int numSquares(int n) {
int[] dp = new int[n + 1];
// Inicialização: O pior caso é usar 'i' vezes o número 1.
for (int i = 0; i <= n; i++) {
dp[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}