Variación sobre el Problema de la Mochila en Programación Dinámica en Java
Publicado por Daniel (6 intervenciones) el 08/05/2016 11:30:08
Buenas, tengo hecho el típico Problema de la mochila de la toda la vida en Java, que consiste en: Se desea llenar la mochila con N objetos. Para ello, se cuenta con una lista de objetos, en la que cada uno tiene un peso y un valor asignado. El número de unidades disponibles de cada tipo de los objetos está limitado, ya que hay un número máximo de cada tipo y se desea maximizar el valor total.
Ahora llega mi duda, lo que yo quiero hacer es que en vez de maximizar el valor total, lo que quiero es que minimice.
Debajo de este primer código indico algunas cosas que yo creo que habría que cambiar (como el getTipo y seleccionAlternativa ponerlas a min, y el getObjetivo y getObjetivoEstimado son los que no se como cambiarlo).
Os adjunto el código que tengo del problema de la mochila es en Programación Dinámica.
La solución que hay es para maximizar y para poder minimizar hay que cambiar también los métodos: getTipo a MIN , el selecciona alternativa también a min, pero creo que también hay que cambiar el getObjetivo y getObjetivoEstimado para que me devuelva una cota minima, pero eso ya no se como cambiarlo y es mi duda, a ver si me pueden ayudar.
También os adjunto la clase ObjetoMochila, que tiene las propiedades de los objetos que se añaden a la mochila.
Ahora llega mi duda, lo que yo quiero hacer es que en vez de maximizar el valor total, lo que quiero es que minimice.
Debajo de este primer código indico algunas cosas que yo creo que habría que cambiar (como el getTipo y seleccionAlternativa ponerlas a min, y el getObjetivo y getObjetivoEstimado son los que no se como cambiarlo).
Os adjunto el código que tengo del problema de la mochila es en Programación Dinámica.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
public class ProblemaMochilaPD implements ProblemaPD<Multiset<ObjetoMochila>, Integer> {
private static ProblemaMochilaPD problemaInicial;
private static Integer capacidadInicial;
private int index;
private Double valorSolucion = Double.MIN_VALUE;
public static List<Integer> multiplicidadesMaximas;
public static List<ObjetoMochila> objetos;
public static Integer numeroDeObjetos;
public static ProblemaMochilaPD create(String fichero, Integer c) {
ProblemaMochila.leeObjetosDisponibles(fichero);
ProblemaMochilaPD.objetos = ProblemaMochila.getObjetosDisponibles();
ProblemaMochilaPD.numeroDeObjetos = ProblemaMochilaPD.objetos.size();
ProblemaMochilaPD.multiplicidadesMaximas = ProblemaMochila.getObjetosDisponibles()
.stream().mapToInt(x->x.getNumMaxDeUnidades())
.boxed()
.collect(Collectors.toList());
ProblemaMochilaPD.capacidadInicial = c;
ProblemaMochilaPD.problemaInicial = new ProblemaMochilaPD(0, 0, 0.);
return ProblemaMochilaPD.problemaInicial; }public static ProblemaMochilaPD create(int index,int pesoAcumulado,double valorAcumulado) {
ProblemaMochilaPD p = new ProblemaMochilaPD(index, pesoAcumulado,valorAcumulado);
return p;
}private Integer pesoAcumulado;
private Integer capacidadRestante;
private Double valorAcumulado;
private ProblemaMochilaPD(int index, int pesoAcumulado, double valorAcumulado) {
this.index = index;
this.pesoAcumulado = pesoAcumulado;
this.capacidadRestante = capacidadInicial-this.pesoAcumulado;
this.valorAcumulado = valorAcumulado;
}private Boolean constraints(Integer a) {
return this.pesoAcumulado+a*objetos.get(index).getPeso() <= capacidadInicial;
}@Override
public Tipo getTipo(){
return Tipo.Max; }@Override
public int size() {
return ProblemaMochilaPD.numeroDeObjetos-index+1;
}@Override
public List<Integer> getAlternativas() {
List<Integer> ls = IntStream.rangeClosed(0, ProblemaMochilaPD.multiplicidadesMaximas.get(this.index))
.filter(x->this.constraints(x))
.boxed()
.collect(Collectors.toList());
Collections.reverse(ls);
return ls;
}@Override
public boolean esCasoBase() {
return this.capacidadRestante == 0 || index == ProblemaMochilaPD.numeroDeObjetos-1;
}@Override
public Sp<Integer> getSolucionCasoBase() {
Integer peso = objetos.get(index).getPeso();
int num = Math.min(capacidadRestante/peso,objetos.get(index).getNumMaxDeUnidades()) ;
Double val = (double) num*objetos.get(index).getValor();
valorSolucion = val;return Sp.create(num, val);
}@Override
public ProblemaPD<Multiset<ObjetoMochila>, Integer> getSubProblema(Integer a, int np) {
Preconditions.checkArgument(np==0);
Integer pesoAcumulado = this.pesoAcumulado+a*objetos.get(index).getPeso();
Double valorAcumulado = this.valorAcumulado+a*objetos.get(index).getValor();
return ProblemaMochilaPD.create(index+1,pesoAcumulado,valorAcumulado);
}@Override
public Sp<Integer> combinaSolucionesParciales(Integer a, List<Sp<Integer>> ls) {
Sp<Integer> r = ls.get(0);
Double valor = a*objetos.get(index).getValor()+r.propiedad;
return Sp.create(a, valor);
}@Override
public Sp<Integer> seleccionaAlternativa(List<Sp<Integer>> ls) {
Sp<Integer> r =ls.stream().filter(x -> x.propiedad != null).max(Comparator.naturalOrder()).orElse(null);
valorSolucion = r!=null ? r.propiedad : Double.MIN_VALUE;
return r;
}@Override
public int getNumeroSubProblemas(Integer a) {
return 1;
}@Override
public Multiset<ObjetoMochila> getSolucionReconstruida(Sp<Integer> sp) {
Multiset<ObjetoMochila> m = HashMultiset.create();
m.add(ProblemaMochilaPD.objetos.get(this.index), sp.alternativa);
return m;
}@Override
public Multiset<ObjetoMochila> getSolucionReconstruida(Sp<Integer> sp, List<Multiset<ObjetoMochila>> ls) {
Multiset<ObjetoMochila> m = ls.get(0);
m.add(ProblemaMochilaPD.objetos.get(this.index), sp.alternativa);
return m;
}@Override
public Double getObjetivoEstimado(Integer a) {
return this.valorAcumulado+this.getCotaSuperiorValorEstimado(a);
}@Override
public Double getObjetivo() {
return this.valorAcumulado+this.valorSolucion;
} /**
* @pre a está contenida en getAlternativas()
* @param a Una alternativa de this
* @return Una cota superior del valor de la solución del problema this si se escoge la alternativa a
*/public Integer getCotaSuperiorValorEstimado(Integer a){
Double r = 0.;
Double capacidadRestante = (double) (capacidadInicial-pesoAcumulado);
Double nu =(double) a;
int ind = this.index;
while(true) {
r = r+nu*objetos.get(ind).getValor();
capacidadRestante = capacidadRestante-nu*objetos.get(ind).getPeso();
ind++;
if(ind >= objetos.size() || capacidadRestante <= 0.) break;
nu = Math.min(multiplicidadesMaximas.get(ind),capacidadRestante/objetos.get(ind).getPeso());
}return (int)Math.ceil(r);
}@Override
public int hashCode() {
final int prime = 31; int result = 1; result = prime * result+ ((capacidadRestante == null) ? 0 : capacidadRestante
.hashCode());
result = prime * result + index;
return result;
}@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof ProblemaMochilaPD))
return false;
ProblemaMochilaPD other = (ProblemaMochilaPD) obj;
if (capacidadRestante == null) {
if (other.capacidadRestante != null)
return false;
} else if (!capacidadRestante.equals(other.capacidadRestante))
return false;
if (index != other.index)
return false;
return true;
}@Override
public String toString() {
return "(" + index + ", "
+ capacidadRestante + ")";
}}La solución que hay es para maximizar y para poder minimizar hay que cambiar también los métodos: getTipo a MIN , el selecciona alternativa también a min, pero creo que también hay que cambiar el getObjetivo y getObjetivoEstimado para que me devuelva una cota minima, pero eso ya no se como cambiarlo y es mi duda, a ver si me pueden ayudar.
También os adjunto la clase ObjetoMochila, que tiene las propiedades de los objetos que se añaden a la mochila.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class ObjetoMochila implements Comparable<ObjetoMochila>{
public static ObjetoMochila create(Integer valor,Integer peso, Integer countMax) {
return new ObjetoMochila(valor, peso, countMax);
}public static ObjetoMochila create(String s) {
return new ObjetoMochila(s);
} private static Integer nCodigo = 0;private Integer codigo;
private Integer valor;
private Integer peso;
private Integer numMaxDeUnidades;
ObjetoMochila(Integer valor, Integer peso, Integer countMax){
this.codigo = nCodigo;
nCodigo++;
this.valor = valor;
this.peso = peso;
this.numMaxDeUnidades = countMax;
}ObjetoMochila(String s){
String[] v = s.split("[ ,]");
Integer ne = v.length;
if(ne != 3) throw new IllegalArgumentException("Formato no adecuado en línea "+s);
valor = new Integer(v[0]);
peso = new Integer(v[1]);
numMaxDeUnidades = new Integer(v[2]);
this.codigo = nCodigo;
nCodigo++;
}public Integer getPeso() {
return peso;
}public Integer getValor() {
return valor;
}public Integer getCodigo() {
return codigo;
}public Integer getNumMaxDeUnidades() {
return numMaxDeUnidades;
}@Override
public int compareTo(ObjetoMochila o) {
int r = getRatioValorPeso().compareTo(o.getRatioValorPeso());
if(r == 0){
r = getCodigo().compareTo(o.getCodigo());
}return r;
}public Double getRatioValorPeso() {
return ((double)valor)/peso;
}@Override
public String toString() {
return "<"+codigo+","+valor+","+peso+","+numMaxDeUnidades+">";
}@Override
public int hashCode() {
final int prime = 31; int result = 1;result = prime * result + ((codigo == null) ? 0 : codigo.hashCode());
return result;
}@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof ObjetoMochila))
return false;
ObjetoMochila other = (ObjetoMochila) obj;
if (codigo == null) {
if (other.codigo != null)
return false;
} else if (!codigo.equals(other.codigo))
return false;
return true;
}}Valora esta pregunta
0