Usando Test::LectroTest::Generator en Algorithm::Knap01DP

El módulo Test::LectroTest::Generator puede ser usado para generar entradas cuya solución sea conocida y de esta forma comprobar el buen funcionamiento del algoritmo.

En el ejemplo que sigue (fichero t/03lectro.t) se generan problemas de 10 objetos con los beneficios (profits) iguales a los pesos. Después se genera un conjunto solución (líneas 15-19). Al elegir la capacidad de la mochila igual a la suma de los pesos del subconjunto generado podemos estar seguros que dicho subconjunto es una solución y que el valor óptimo es igual a la capacidad. De hecho este subproblema de la mochila es conocido como problema del subconjunto suma (Subset Sum Problem o SSP).

lhp@nereida:~/Lperl/src/perl_testing_adn_examples/chapter_03/Algorithm-Knap01DP-0.25$ cat -n t/03lectro.t
 1  use strict;
 2  use Test::More;
 3  use Test::LectroTest::Generator qw(:common);
 4  use List::Util qw(sum);
 5
 6  use Algorithm::Knap01DP;
 7
 8  my $t = shift || 100;
 9  plan tests => $t;
10  my ($C, @sol);
11  for (1..$t) {
12    my $weights = List(Int(range => [5,100], sized=>0), length => 10);
13    my @w = @{$weights->generate};
14    my @p = @w;
15    my $set = List(Bool, length => 10);
16    do {
17      @sol = @{$set->generate};
18      $C = sum( @w[ grep { $sol[$_] } 0..9 ] );
19    } while ($C == 0);
20    my $knap = Algorithm::Knap01DP->new( capacity => $C, weights => \@w, profits => \@p);
21    $knap->Knap01DP();
22    is($C, $knap->{tableval}[-1][-1], "Random subset-sum problem");
23  }

Observe como el uso de plan en la línea 9 nos permite ajustar dinámicamente el número de pruebas a ejecutar. Podemos hacer una ejecución vía make:

lhp@nereida:~/Lperl/src/perl_testing_adn_examples/chapter_03/Algorithm-Knap01DP-0.25$ make test
PERL_DL_NONLAZY=1 /usr/bin/perl "-MExtUtils::Command::MM" "-e" "test_harness(0, 'blib/lib', 'blib/arch')" t/*.t
t/01alltests....ok
t/02bench.......ok
t/03lectro......ok
All tests successful.
Files=3, Tests=116,  4 wallclock secs ( 4.08 cusr +  0.02 csys =  4.10 CPU)

o una ejecución ''manual'':

lhp@nereida:~/Lperl/src/perl_testing_adn_examples/chapter_03/Algorithm-Knap01DP-0.25/t$ perl 03lectro.t 4
1..4
ok 1 - Random subset-sum problem
ok 2 - Random subset-sum problem
ok 3 - Random subset-sum problem
ok 4 - Random subset-sum problem