Problema da mochila: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Etiqueta: gettingstarted edit |
Etiqueta: gettingstarted edit |
||
Linha 118:
<source lang="java">
public class mochila_limitado{
public static void
Linha 170 ⟶ 169:
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();
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];
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){
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>
| |||