|
[[Imagem:Knapsack.svg|thumb|Problema da mochila: Como maximizar o valor com um peso máximo?]]
[[File:Mochilaproblema.png|thumb|Problema da Mochila acima resolvido no Processing.]]
O '''problema da mochila''' (em [[Língua inglesa|inglês]], ''Knapsack problem'') é um problema de [[optimização combinatória]]. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.<ref> Xinjie Yu,Mitsuo Ge, ''Introduction to Evolutionary Algorithms'', p.270-271</ref>
se <math>w_{j} > w</math>: <math>K(w,j) = K(w,j-1)</math>
senão: <math>K(w,j) = \max\{ K(w,j-1), K(w-w_{j},j-1) + v_{j}\}</math>
retornar <math>K(W,n)</math><br>
== Implementações ==
'''Código em java para o problema limitado'''
<source lang="java">
//O StdIn poder ser pego no Site http://introcs.cs.princeton.edu/java/stdlib/StdIn.java.html
public class mochila_limitado{
public static void
main( String[]arg){
int n = StdIn.readInt();
int W = StdIn.readInt();
W = W + 1;
n = n + 1;
int solucao[] = new int [n];
double valor[] = new double [n];
int pesos[] = new int [n];
int a = 1;
while(a<n){
valor[a] = StdIn.readDouble();
pesos[a] = StdIn.readInt();
a = a + 1;}
double valor_otimo[][] = new double[W][n];
double keep[][] = new double[W][n];
int j = 1;
int peso = 1;
a = 0;
while(j<n){
peso = 1;
while(peso<W){
if(pesos[j]>peso){
valor_otimo[peso][j] = valor_otimo[peso][j-1];}
if(pesos[j] <=peso){
if(valor_otimo[peso][j-1] <= valor_otimo[peso - pesos[j]][j-1] + valor[j]){
valor_otimo[peso][j] = valor_otimo[peso - pesos[j]][j-1] + valor[j];
keep[peso][j]= 1;}
if(valor_otimo[peso][j-1] > valor_otimo[peso - pesos[j]][j-1] +valor[j]){
valor_otimo[peso][j]= valor_otimo[peso][j-1];}
}
peso = peso + 1;}
j = j + 1;
}
int item = n-1;
int remaning_weight = W-1;
System.out.println("os itens a serem levados são:");
while(item!=0){
if(keep[remaning_weight][item] == 1){
remaning_weight = remaning_weight - pesos[item];
solucao[a] =item;
System.out.println(solucao[a]);
a = a + 1;}
item = item - 1;}
double otimo = valor_otimo[W-1][n-1];
System.out.println("o maior valor possível é " + otimo);
}}
</source>
'''Código em java para o problema ilimitado'''
<source lang="java">
public class mochila_ilimitado{
public static void main( String[]arg){
int n = StdIn.readInt();
int W = StdIn.readInt();
W = W + 1;
n = n + 1;
int b = 1;
int c = 1;
int soma = 1;
double valor_1[] = new double [n];
int pesos_1[] = new int [n];
int rep[] = new int[n-1];
int a = 1;
while(a<n){
valor_1[a] = StdIn.readDouble();
pesos_1[a] = StdIn.readInt();
rep[a-1] = ((int)(W/(pesos_1[a])));
soma = soma +
rep[a-1];
a = a + 1;}
a = 0;
double valor[] = new double [soma];
int pesos[] = new int [soma];
int memoria[] = new int [soma];
while(a<n-1){
c = 1;
while(c < rep [a] +1){
valor[b] = valor_1[a+1];
pesos[b] =
pesos_1[a+1];
memoria[b] = a + 1;
b = b + 1;
c = c + 1;}
a = a + 1;
}
double valor_otimo[][] = new double[W][soma];
double keep[][] = new double[W][soma];
int j = 1;
int peso = 1;
a = 0;
while(j<soma){
peso = 1;
while(peso<W){
if(pesos[j]>peso){
valor_otimo[peso][j] = valor_otimo[peso][j-1];}
if(pesos[j]<= peso){
if(valor_otimo[peso][j-1] <= valor_otimo[peso - pesos[j]][j-1] + valor[j]){
valor_otimo[peso][j] = valor_otimo[peso - pesos[j]][j-1] + valor[j];
keep[peso][j] = 1;}
if(valor_otimo[peso][j-1] > valor_otimo[peso - pesos[j]][j-1] +valor[j]){
valor_otimo[peso][j] = valor_otimo[peso][j-1];}
}
peso = peso + 1;}
j = j + 1;
}
int item = soma-1;
int remaning_weight = W-1;
System.out.println("os itens a serem levados são:");
while(item!=0){
if(keep[remaning_weight][item] == 1){
remaning_weight = remaning_weight -
pesos[item];
System.out.println(memoria[item]);
}
item = item - 1;
}
double otimo = valor_otimo[W-1][soma-1];
System.out.println("o maior valor possível é " + otimo);
}}
</source>
=== Código python problema ilimitado ===
<source lang="python">
//peso é uma lista de pesos
//valores é uma lista de valores
//W é a capacidade da mochila
def knapsack(W,peso,valores):
K = [0 for i in range(W+1)]
n = len(valores)
maximo = 0
for w in range(1,W+1):
for i in range(n):
if peso[i]<=w:
maximo = max(K[w-peso[i]] + valores[i],maximo)
K[w]= maximo
return K[W]
</source>
=== Solução usando Backtracking ===
| 