File perl-Algorithm-Knap01DP.spec of Package perl-Algorithm-Knap01DP

#
# spec file for package perl-Algorithm-Knap01DP
#
# Copyright (c) 2016 SUSE LINUX GmbH, Nuernberg, Germany.
#
# All modifications and additions to the file contributed by third parties
# remain the property of their copyright owners, unless otherwise agreed
# upon. The license for this file, and modifications and additions to the
# file, is the same license as for the pristine package itself (unless the
# license for the pristine package is not an Open Source License, in which
# case the license is the MIT License). An "Open Source License" is a
# license that conforms to the Open Source Definition (Version 1.9)
# published by the Open Source Initiative.

# Please submit bugfixes or comments via http://bugs.opensuse.org/
#


Name:           perl-Algorithm-Knap01DP
Version:        0.25
Release:        0
%define cpan_name Algorithm-Knap01DP
Summary:        Solves the 0-1 Knapsack problem using the Dynamic Programming Technique
License:        GPL-1.0+ or Artistic-1.0
Group:          Development/Libraries/Perl
Url:            http://search.cpan.org/dist/Algorithm-Knap01DP/
Source0:        http://www.cpan.org/authors/id/C/CA/CASIANO/%{cpan_name}-%{version}.tar.gz
BuildArch:      noarch
BuildRoot:      %{_tmppath}/%{name}-%{version}-build
BuildRequires:  perl
BuildRequires:  perl-macros
%{perl_requires}

%description
Solves the 0-1 Knapsack problem using the Dynamic Programming Technique.
See an example of problem format

    $ cat knapanderson.dat
    6   # number of objects
    30  # capacity
    14  # weight object 0
    14  # profit object 0
    5   # etc.
    5
    2
    2
    11
    11
    3
    3
    8
    8

This corresponds to a problem with N=6, M=30 (objects, capacity) then the
following consecutive pair of lines hold the weight and profit (in that
order) of the different objects. A program illustrating the use of the
module follows:

    $ cat -n example.pl
    1  use strict;
    2  use Algorithm::Knap01DP;
    3
    4  die "Usage:\n$0 knapsackfile\n" unless @ARGV;
    5  my $knap = Algorithm::Knap01DP->ReadKnap($ARGV[0]);
    6  $knap->solutions();
    7  $knap->ShowResults();

The output is:

    $ perl example.pl knapanderson.dat
    Problem: knapanderson.dat
    Number of Objects = 6 Capacity = 30
    0 (14)  1 (5)   4 (3)   5 (8)   Used Capacity = 30
    0 (14)  2 (2)   3 (11)  4 (3)   Used Capacity = 30
    0 (14)  1 (5)   3 (11)  Used Capacity = 30
    Profit = 30

The algorithm has complexity order M x N, being M the capacity and N the
number of objects. Since M is usually much smaller than 2^N, the algorithm
gives a efficient way to find all the solutions.

%prep
%setup -q -n %{cpan_name}-%{version}

%build
%{__perl} Makefile.PL INSTALLDIRS=vendor
%{__make} %{?_smp_mflags}

%check
%{__make} test

%install
%perl_make_install
%perl_process_packlist
%perl_gen_filelist

%files -f %{name}.files
%defattr(-,root,root,755)
%doc Changes README TODO

%changelog