Although Abigail is correct (NP complete problems like this one have no efficient solutions for large sets of data), you still can create software which runs it fast.

At least there are two ways to improve it:

1. implement and algorithm which is smarter than branch-and-bound. A lot of work, requires sufficient education in programming techniques.
2. exchange required computation force with memory consumption. Use Memoize (by MJ Dominous) on KNAP and you'll see the the speed become linear and memory consumption grow exponentially... In some cases, you may be able to buy a sufficient amount of memory to replace unrealistic time to wait. (for instance, for stock calculations, minutes may already be too long to wait)

Sorry, but the code you have posted isn't even legal perl.

P:\test>perl -c temp.pl
Scalar value @lite[] better written as $lite[] at temp.pl line 7.
Scalar value @list[] better written as $list[] at temp.pl line 37.
syntax error at temp.pl line 7, near "@lite["
syntax error at temp.pl line 37, near "@list["
Global symbol "$i" requires explicit package name at temp.pl line 42.
Global symbol "$maxlites" requires explicit package name at temp.pl li
+ne 42.
Global symbol "$i" requires explicit package name at temp.pl line 42.
syntax error at temp.pl line 42, near "++;"
Global symbol "$i" requires explicit package name at temp.pl line 44.
Global symbol "$i" requires explicit package name at temp.pl line 46.
Global symbol "$i" requires explicit package name at temp.pl line 46.
Global symbol "$i" requires explicit package name at temp.pl line 47.
Global symbol "$i" requires explicit package name at temp.pl line 54.
Global symbol "$i" requires explicit package name at temp.pl line 54.
Global symbol "$i" requires explicit package name at temp.pl line 55.
Global symbol "$j" requires explicit package name at temp.pl line 66.
Global symbol "$j" requires explicit package name at temp.pl line 66.
Global symbol "$j" requires explicit package name at temp.pl line 66.
Global symbol "$j" requires explicit package name at temp.pl line 67.
Global symbol "$j" requires explicit package name at temp.pl line 68.
Global symbol "$j" requires explicit package name at temp.pl line 69.
Global symbol "$j" requires explicit package name at temp.pl line 71.
Global symbol "$j" requires explicit package name at temp.pl line 72.
Global symbol "$j" requires explicit package name at temp.pl line 73.
Global symbol "$j" requires explicit package name at temp.pl line 73.
Global symbol "$j" requires explicit package name at temp.pl line 74.
Global symbol "$k" requires explicit package name at temp.pl line 77.
Global symbol "$k" requires explicit package name at temp.pl line 77.
Global symbol "$maxlites" requires explicit package name at temp.pl li
+ne 77.
Global symbol "$k" requires explicit package name at temp.pl line 77.
Global symbol "$k" requires explicit package name at temp.pl line 81.
Global symbol "$j" requires explicit package name at temp.pl line 88.
Global symbol "$j" requires explicit package name at temp.pl line 88.
Global symbol "$newx" requires explicit package name at temp.pl line 9
+1.
Global symbol "$j" requires explicit package name at temp.pl line 91.
Global symbol "$newy" requires explicit package name at temp.pl line 9
+2.
Global symbol "$j" requires explicit package name at temp.pl line 92.
Global symbol "$newx" requires explicit package name at temp.pl line 9
+4.
Global symbol "$newy" requires explicit package name at temp.pl line 9
+4.
Global symbol "$newy" requires explicit package name at temp.pl line 9
+5.
Global symbol "$newx" requires explicit package name at temp.pl line 9
+6.
Global symbol "$j" requires explicit package name at temp.pl line 96.
Global symbol "$j" requires explicit package name at temp.pl line 96.
Global symbol "$j" requires explicit package name at temp.pl line 97.
Global symbol "$newy" requires explicit package name at temp.pl line 9
+7.
Global symbol "$j" requires explicit package name at temp.pl line 97.
Global symbol "$newx" requires explicit package name at temp.pl line 9
+8.
Global symbol "$j" requires explicit package name at temp.pl line 98.
temp.pl had compilation errors.
[download]

It looks like you have attempted a brute force conversion of a C program, but you don't have enough knowledge of Perl syntax to make the conversion.

Taking on (or being given) a complex, near impossible task to program, in language you do not understand enough to recognise that

...or die ("could not open file. &!" );
[download]

should be ...die ("could not open file.$!" );

or my @lite[][]; just isn't legal perl syntax.

means that you are trying to run before you can walk.

You need to start with smaller problems and learn the syntax first.

Attempting to leap in and asking for help to solve one of the toughest problems in computing, when you do not yet know the basic syntax is not going to get you very far. Even if someone was interested enough to take their time to re-write your program and make it work, you would have learned nothing.

I apologize for my lack of skills. I started by just writing code, not in any specific language, and thus in my haste, I did not pay attention to the details of my program. For that I apologize. If someone could look through my program, I am looking for a way to use the variable $waste to determine which set of rectangle locations should be used. I am trying to minimize $waste.

use strict;
use warnings;
use Data::Dumper;

open ( OHA, ">c:/printoutKNAP.txt" ) or die ("could not open file. &!"
+ );


$lite[0][0] = 2;
$lite[0][1] = 5;
$lite[0][2] = 0;
$lite[0][3] = 0;
$lite[0][4] = 0;

$lite[1][0] = 4;
$lite[1][1] = 3;
$lite[1][2] = 0;
$lite[1][3] = 0;
$lite[1][4] = 0;

$lite[2][0] = 1;
$lite[2][1] = 4;
$lite[2][2] = 0;
$lite[2][3] = 0;
$lite[2][4] = 0;

my $waste = 0;
my $end = 0;
my $maxlites = 3;

sub KNAP {
  
  my $bigx = $_[0];
  my $bigy = $_[1];
  my $locx = $_[2];
  my $locy = $_[3];

  my $list[$maxlites][4];

  my $listnum = 0;


  for ( my $i = 1; i <= $maxlites; $i ++; ) {

    if ( $lite[$i][2] == 0 ) {

      if ( ( $lite[$i][0] <= $bigx ) && ( $lite[$i][1] <= $bigy ) ) {
    $list[$listnum][0] = $i;
    $list[$listnum][1] = 0;
    $list[$listnum][2] = 0;
    $listnum = $listnum + 1;

      }

      if ( ( $lite[$i][1] <= $bigx ) && ( $lite[$i][0] <= $bigy ) ) {
    $list[$listnum][0] = $i;
    $list[$listnum][1] = 0;
    $list[$listnum][2] = 1;
    $listnum = $listnum + 1;

      }

    }

  }

  for ( my $j = 1; $j <= $listnum; $j++ ) {
    $list[$list[$j][0]][2] = 1;
    $list[$list[$j][0]][3] = $locx;
    $list[$list[$j][0]][4] = $locy;

    if ( $list[$j][2] == 1 ) {
      my $temp = $lite[$list[$j][0]][0];
      $lite[$list[$j][0]][0] = $lite[$list[$j][0]][1];
      $list[$list[$j][0]][1] = $temp;
    }

    select OHA;
    for ( my $l = 1; $l <= $maxlites; $l++ ) {
      print "locx $lite[$l][3] locy $lite[$l][4]/n";
    }
    select STDOUT;


    for ( my $k = 1; $k <= $maxlites; $k++ ) {

      $end = 1;

      if ( $lite[$k][2] == 0 ) {
        $end = 0;
      }

    }

    if ( $end == 1 ) {
      $waste = $waste + ( $bigx*$bigy - $lite[$list[$j][0]][0]*$lite[$
+list[$j][0]][1] );
    }

    my $newx = $bigx - $lite[$list[$j][0]][0];
    my $newy = $bigy - $lite[$list[$j][0]][1];

    if ( ( $newx != 0 ) && ( $newy != 0 ) && ( $end != 1 ) ) {
      &KNAP( $bigx, $newy, $locx, $locy + $lite[$list[j][0]][1] );
      &KNAP( $newx, $lite[$list[$j][0]][1], $locx + $lite[$list[$j][0]
+][0], $locy );
      &KNAP( $lite[$list[$j][0]][0], $newy, $locx, $locy + $lite[$list
+[$j][0]][1] );
      &KNAP( $newx, $bigy, $locx + $lite[$list[$j][0]][0], $locy );
    }
  
  }

}

&KNAP ( 10, 10, 0, 0 );
[download]

"...the code you have posted isn't even legal perl"

Are the Perl police going to throw him in a chroot jail? :P

(Sorry... I could not resist.)

-Lee

"To be civilized is to deny one's nature."

Here is actual legal perl code, but I still need help. So could someone look at it and please help me out. Thank you very much.

use strict;
use warnings;
use Data::Dumper;

open ( OHA, ">c:/printoutKNAP.txt" ) or die ("could not open file. &!"
+ );

my @lite;

$lite[0][0] = 2;
$lite[0][1] = 5;
$lite[0][2] = 0;
$lite[0][3] = 0;
$lite[0][4] = 0;

$lite[1][0] = 4;
$lite[1][1] = 3;
$lite[1][2] = 0;
$lite[1][3] = 0;
$lite[1][4] = 0;

$lite[2][0] = 1;
$lite[2][1] = 4;
$lite[2][2] = 0;
$lite[2][3] = 0;
$lite[2][4] = 0;

my $waste = 0;
my $end = 0;
my $maxlites = 3;

sub KNAP {
  
  my $bigx = $_[0];
  my $bigy = $_[1];
  my $locx = $_[2];
  my $locy = $_[3];

  my @list;

  my $listnum = 0;


  for my $i ( 0..$#lite ) { 

    if ( $lite[$i][2] == 0 ) {

      if ( ( $lite[$i][0] <= $bigx ) && ( $lite[$i][1] <= $bigy ) ) {
    $list[$listnum][0] = $i;
    $list[$listnum][1] = 0;
    $list[$listnum][2] = 0;
    $listnum = $listnum + 1;

      }

      if ( ( $lite[$i][1] <= $bigx ) && ( $lite[$i][0] <= $bigy ) ) {
    $list[$listnum][0] = $i;
    $list[$listnum][1] = 0;
    $list[$listnum][2] = 1;
    $listnum = $listnum + 1;

      }

    }

  }

  for my $j ( 0..$#list ) {

    if ( $list[$j][2] == 1 ) {
      my $temp = $lite[$list[$j][0]][0];
      $lite[$list[$j][0]][0] = $lite[$list[$j][0]][1];
      $lite[$list[$j][0]][1] = $temp;
    }

    $lite[$list[$j][0]][2] = 1;
    $lite[$list[$j][0]][3] = $locx;
    $lite[$list[$j][0]][4] = $locy;

    select OHA;
    for my $l ( 0..$#lite ) {
      print "locx $lite[$l][3] locy $lite[$l][4]\n";
    }
    select STDOUT;


    for my $k ( 0..$#lite ) {

      $end = 1;

      if ( $lite[$k][2] == 0 ) {
        $end = 0;
      }

    }

    if ( $end == 1 ) {
      $waste = $waste + ( $bigx*$bigy - $lite[$list[$j][0]][0]*$lite[$
+list[$j][0]][1] );
    }

    my $newx = $bigx - $lite[$list[$j][0]][0];
    my $newy = $bigy - $lite[$list[$j][0]][1];

    if ( ( $newx != 0 ) && ( $newy != 0 ) && ( $end != 1 ) ) {
      &KNAP( $bigx, $newy, $locx, $locy + $lite[$list[$j][0]][1] );
      &KNAP( $newx, $lite[$list[$j][0]][1], $locx + $lite[$list[$j][0]
+][0], $locy );
      &KNAP( $lite[$list[$j][0]][0], $newy, $locx, $locy + $lite[$list
+[$j][0]][1] );
      &KNAP( $newx, $bigy, $locx + $lite[$list[$j][0]][0], $locy );
    }
  
  }

}

&KNAP ( 10, 10, 0, 0 );
[download]

If you really must solve this, and it should be done fast, do a literature study, and implement one of the faster algorithms you'll see. In C.

Abigail

Given that he knows the name of the problem and the method to solve it fairly effectively (Branch N' Bound) suggest he already knows this and is simply interested in some help with the specific implementation...


T I M T O W T D I

Either that, or he's having problems completing his homework...