El Problema de la mochila 0-1

Utilizando programación dinámica es posible resolver el problema de la mochila 0-1: Se tiene una mochila de de capacidad $M$ y $N$ objetos de pesos $w_k$ y beneficios $p_k$ . Se trata de encontrar la combinación óptima de objetos que caben en la mochila y producen el máximo beneficio. Para ello denotemos por $f_k(c)$ el beneficio óptimo obtenido usando los primeros $k$ objetos y una mochila de capacidad $c$ . Entonces $f_0(c) = p_0$ si $c \ge w_0$ y 0 en otro caso. Además

$f_k(c) = \max \{ f_{k-1}(c), f_k-1(c-w_k)+p_k \}$ si $c > w_k$ y $f_k(c) = f_{k-1}(c)$ en otro caso.

El esquema del algoritmo secuencial es:

  for my $c (0..$M) {
    $f[0][$c] = ($w[0] <= $c)? $p[0] : 0;
  }

  for my $k (1..$N-1) {
    for my $c (0..$M) {
      my $n = $f[$k-1][$c];
      if ($c >= $w[$k]) {
        my $y = $f[$k-1][$c-$w[$k]]+$p[$k];
        $f[$k][$c] = ($n < $y)? $y : $n;
      }
      else { $f[$k][$c] = $n; }
    }
  }

En la dirección:

http://nereida.deioc.ull.es/˜lhp/perlexamples/Algorithm-Knap01DP-0.01.tar.gz.

puede encontrar una distribución de un módulo Perl que proporciona una solución secuencial.

He aqui una solución paralela:

$ cat -n pipeknap.pl
 1  #!/usr/bin/perl -w -I../lib
 2  # File: pipeknap.pl
 3
 4  use strict;
 5  use threads;
 6  use Thread::Queue;
 7  use Carp;
 8  use IO::File;
 9  use Threads::Pipe qw(pipe);
10
11  ### main
12  #my ($M, $w, $p) = ReadKnap($ARGV[0]);
13  srand(27);
14  my ($M, $w, $p) = GenKnap($ARGV[0]);
15  my $N = @$w;
16  my $numthreads = ($ARGV[1] || 2);
17
18  my @f = &pipe($numthreads, $N, \&knap, $M, $w, $p);
19
20  my @Table = GetSol(@f);
21  print "Sol = $Table[-1][-1]\n";
22
23  sub knap {
24    my $k = shift();
25    my $from_left = shift();
26    my $to_right = shift();
27    ##############
28    my $M = shift();
29    my @w = @{shift()};
30    my @p = @{shift()};
31
32    my $N = @w;
33    my @f;
34    my @left;
35
36    croak "Profits and Weights don't have the same size" unless scalar(@w) == scalar(@p);
37
38    if ($k) {
39      for my $c (0..$M) {
40        $left[$c] = $from_left->dequeue();
41        if ($c >= $w[$k]) {
42          my $y = $left[$c-$w[$k]]+$p[$k];
43          $f[$c] = ($left[$c] < $y)? $y : $left[$c];
44        }
45        else {
46          $f[$c] = $left[$c];
47        }
48        $to_right->enqueue($f[$c]);
49      }
50    }
51    else { # thread virtual 0
52      for my $c (0..$M) {
53        $f[$c] = ($w[0] <= $c)? $p[0] : 0;
54      }
55      $to_right->enqueue(@f);
56    }
57    return (\@f);
58  }
59
60  sub ReadKnap {
61    my $filename = shift;
62
63    my $file = IO::File->new("< $filename");
64    croak "Can't open $filename" unless defined($file);
65    my (@w, @p);
66
67    my ($N, $M);
68
69    chomp($N = <$file>);
70    chomp($M = <$file>);
71    for (0..$N-1) {
72      $w[$_] = <$file>;
73      $p[$_] = <$file>;
74    }
75    chomp @w;
76    chomp @p;
77    $file->close();
78    return ($M, \@w, \@p);
79  }
80
81  sub GenKnap {
82    my $N = (shift() || 10000);
83    my $R = (shift() || $N);
84
85    my ($x, $M, @w);
86    @w = map { $x = 1 + int(rand($R)); $M += $x; $x } 1..$N;
87    $M = int ($M / 2);
88    return ($M, \@w, \@w);
89  }
90
91  sub GetSol {
92    my @f = @_;
93
94    my $k = 0;
95    for my $t (@f) {
96      my $c = 0;
97      for my $fkc (@$t) {
98        $Table[$k][$c] = $fkc;
99        $c++;
100      }
101    $k++;
102    }
103    return @Table;
104  }