Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Help with attempting to solve cutting stock problem (knapsack)

by stu96art (Scribe)
on Jan 16, 2004 at 16:24 UTC ( [id://321817]=perlquestion: print w/replies, xml ) Need Help??

stu96art has asked for the wisdom of the Perl Monks concerning the following question:

Here is the code that I have been working on to solve the knapsack problem that I have been looking for so much help with. I need to get this to work, and I think that I am using the branch and bound method, but I can forsee problem with larger amounts of rectangles. So I need help with two things, please 1) Making the code that I have work and 2) Making that code faster, or where it does not go through each possibility. Thank you for any help you can give me.
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; sub KNAP { my $bigx = $_[0]; my $bigy = $_[1]; my $locx = $_[2]; my $locy = $_[3]; my @list[][]; my $listnum = 0; for ( $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 ( $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; } for ( $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] ); } $newx = $bigx - $lite[$list[$j][0]][0]; $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 ); } } }

Replies are listed 'Best First'.
Re: Help with attempting to solve cutting stock problem (knapsack)
by markov (Scribe) on Jan 16, 2004 at 16:51 UTC

    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)
Re: Help with attempting to solve cutting stock problem (knapsack)
by BrowserUk (Patriarch) on Jan 16, 2004 at 17:17 UTC

    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.

    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. &!" );

    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.


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    Timing (and a little luck) are everything!

      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 );
      "...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 );
Re: Help with attempting to solve cutting stock problem (knapsack)
by Abigail-II (Bishop) on Jan 16, 2004 at 16:29 UTC
    The knapsack problem is a well-known problem from the literature. It's also known to be NP-complete, which means that there is no known efficient solution.

    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...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://321817]
Approved by sschneid
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (4)
As of 2024-03-29 00:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found