4.3.1. Problema de la mochila.

Mochila (M: integer; V, W: array [1..N] of integer; var X: array [1..N] of integer);

for i:= 1 to N do

X[i]:= 0;

peso_act:= 0;

while peso_act < M do begin

j:= el mejor objeto restante;

if peso_act + W[i] ? M then begin

X[i]:= 1;

peso_act:= peso_act + W[i];

end

else begin

X[i]:= (M - peso_act)/W[i];

peso_act:= M;

end;

end;

• Criterios para seleccionar el mejor objeto de los restantes:

  1. El objeto con más beneficio vi.
  
  2. El objeto menos pesado wi (para poder añadir muchos objetos).
  3. El objeto con mejor proporción vi/wi (coste por unidad de peso).

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica