#!/usr/bin/perl -w # # This script solves the knapsack problem. # It generates a bunch of random numbers and tries to add them up to 500. # It does this 1000 times and displays the additions... # Written by Zsolt Nagy-Perge in Feb 2022 (zsnp@juno.com). # use strict; use warnings; my $GOAL = 500; my $ARRAY_SIZE = 25; # We will use this many random numbers my $MIN = 1; # ranging from this my $MAX = 100; # to this. # # TESTING SPECIAL CASES: # #@RANDOM_NUMBERS = (1) x $ARRAY_SIZE; #@RANDOM_NUMBERS = (9) x $ARRAY_SIZE; #@RANDOM_NUMBERS = (25) x $ARRAY_SIZE; #@RANDOM_NUMBERS = (251) x $ARRAY_SIZE; #@RANDOM_NUMBERS = ((1) x 10, (2) x 20, (3) x 30, (40) x 20, (999) x 20); #@RANDOM_NUMBERS = ((5) x 5, (6) x 5, (501) x 90); #@RANDOM_NUMBERS = (1, 3, 3, 7, (11) x 90, 30, 40, 60, 90, 100, 160, 250); # THE TRICKY TRAP LIST #@RANDOM_NUMBERS = qw(3 8 18 27 27 34 35 37 41 50 54 61 61 65 65 67 72 85 91 108 112 116 118 121 121 129 133 134 138 145 147 148 148 158 160 183 192 195 197 200 200 201 230 244 246 250 252 259 269 270 270 272 272 276 277 280 285 289 294 304 310 312 313 316 321 323 326 333 347 349 352 354 364 365 369 369 371 387 400 402 402 403 423 424 425 426 427 233 434 441 442 444 460 463 465 479 490 493 493 494 496); # Vlado Keselj's list #my @RANDOM_NUMBERS = qw(81 593 439 339 699 976 588 796 465 123 273 305 898 729 252 315 384 857 237 299 364 921 638 308 198 943 831 532 995 721 210 194 893 663 124 478 312 551 509 369 643 707 831 659 490 909 90 215 774 574 725 711 714 345 593 73 825 930 916 459 691 281 920 447 922 328 336 141 924 350 662 378 905 684 421 759 709 572 283 725 70 399 800 706 562 778 945 862 376 77 371 197 459 143 127 282 664 681 912 55); #@RANDOM_NUMBERS = (1, 4, 8, 9, 21, 21, 44, (49) x 4, (51) x 81, 499); # This takes a little long. #@RANDOM_NUMBERS = (56, 58, 64, 79, 85, 91, 178, (186) x 285, 398); # This is also very slow #@RANDOM_NUMBERS = RandomIntList(100, 20, 242); #@RANDOM_NUMBERS = (250) x $ARRAY_SIZE; #my @RANDOM_NUMBERS = (20, 80, (481) x 70, 300, (482) x 30, 90); #my @RANDOM_NUMBERS; for (my $z = 0; $z < 1500; $z+=23) { push(@RANDOM_NUMBERS, $z); } $| = 1; my $ERRORS = 0; for (my $z = 0; $z < 1000; $z++) { my @RANDOM_NUMBERS = RandomIntList($ARRAY_SIZE, $MIN, $MAX); # DisplayList(@RANDOM_NUMBERS); my @A = SolveKnapSack($GOAL, @RANDOM_NUMBERS); print "\n", $A[0], ' = '; my $SUM = 0; for (my $i = 1; $i < @A; $i++) { print '+', $RANDOM_NUMBERS[$A[$i]], ' '; $SUM += $RANDOM_NUMBERS[$A[$i]]; } if ($A[0] != $SUM) { $ERRORS++; } } #print "\n\nThere were $ERRORS errors.\n"; exit; ################################################## # v2022.2.27 # This function takes an array of positive integers # and tries to figure out the best combination to # add up these numbers so that we reach TOTAL or # some number closest to TOTAL. Returns an ARRAY of # indexes that point to elements of the array that # should be added up. # The first element of this array will contain the # sum that can be reached by adding up all the numbers. # # Usage: ARRAY = SolveKnapSack(TOTAL, LIST_OF_NUMBERS) # sub SolveKnapSack { my @BLANK = (0); @_ >= 2 or return @BLANK; defined $_[0] or return @BLANK; my $GOAL = shift; # Create a copy of the input array and also find the MIN and MAX values. my @NUMBERS; # Numbers will be copied here my ($MIN, $MAX, $MAXPTR) = (999999999999, 0); for (my $i = 0; $i < @_; $i++) { $a = $_[$i]; if ($a < 1 || $a > $GOAL) { next; } # Skip numbers that obviously aren't going to work if ($a == $GOAL) { return ($a, $i); } # We found it already? Wow! push(@NUMBERS, $a * 16777216 + $i); # We store the index along with the number, so they stay together when sorted. if ($a < $MIN) { $MIN = $a; } # Find smallest number if ($a > $MAX) { $MAX = $a; $MAXPTR = $i; } # Find largest number and remember its pointer } my $ALL_THE_SAME = ($MIN == $MAX) ? 1 : 0; # Are all the numbers the same? $ALL_THE_SAME or @NUMBERS = sort { $a <=> $b } @NUMBERS; # Sort numbers (unless they're all the same). # First we will add up all the numbers starting from the least to the greatest. # At the same time, we separate NUMBERS from the index and store # the index numbers separately in an array called @INDEX. # We also record the sum of all numbers up to the 25% mark, the midpoint and the 75% mark. my @INDEX; # This will hold pointers to each number my @OUTPUT = (0); # This will hold the best combination we find my $SUM = 0; for (my $i = 0; $i < @NUMBERS; $i++) { $a = $NUMBERS[$i]; # Numbers have been sorted, so we can separate them again. push(@INDEX, ($b = $a % 16777216)); # Extract the index portion of the number $SUM += ($NUMBERS[$i] = int($a / 16777216)); # Extract the number part, and add to sum if ($SUM <= $GOAL) { $OUTPUT[0] = $SUM; push(@OUTPUT, $b); if ($SUM == $GOAL) { return @OUTPUT; } # Found the solution? } } # Stop if we were able to add up all the numbers OR if all the numbers were the same... if ($#OUTPUT == $#NUMBERS || $ALL_THE_SAME) { return @OUTPUT; } # Any combination of numbers will have to get us closer to our goal. # If not, then we fall back to what's in @OUTPUT. if ($MAX > $OUTPUT[0]) { @OUTPUT = ($MAX, $MAXPTR); } # Now we will add up pairs of numbers starting with the largest first. for (my $i = $#NUMBERS; $i > 0; $i--) { my @SET = (0); $SUM = $NUMBERS[$i] + $NUMBERS[$i-1]; # Add up the largest + the next largest number. # If $SUM is still larger, then keep going down to the next smaller value. # If $SUM is smaller, then we try to add as many large values as possible. if ($SUM <= $GOAL) { $SET[0] = $SUM; push(@SET, $INDEX[$i], $INDEX[$i-1]); if ($SUM == $GOAL) { return @SET; } # Add up all big numbers from now on until we find the closest number. for (my $j = $i - 2; $j >= 0; $j--) { $SUM += $NUMBERS[$j]; if ($SUM <= $GOAL) { $SET[0] = $SUM; push(@SET, $INDEX[$j]); if ($SUM == $GOAL) { return @SET; } } else { # Adding up as many of the biggest numbers has led us here, but now # we can't add anymore big numbers, so let's start adding from the smallest ones. # See, if there's anything we can still fit in here. $SUM = $SET[0]; for (my $k = 0; $k < $j; $k++) { $SUM += $NUMBERS[$k]; if ($SUM <= $GOAL) { $SET[0] = $SUM; push(@SET, $INDEX[$k]); if ($SUM == $GOAL) { return @SET; } } else { $SUM = $SET[0]; last; } } last; } } # If we break the record, then save the new record. if ($SUM > $OUTPUT[0]) { $SET[0] = $SUM; @OUTPUT = @SET; } } } return @OUTPUT; } ################################################## # v2022.2.25 # This function returns a list of N random # integers ranging from MIN to MAX. # # Usage: ARRAY = RandomIntList(N, MIN, MAX) # sub RandomIntList { my ($N, $MIN, $MAX) = @_; my @INTEGERS; for (my $i = 0; $i < $N; $i++) { $INTEGERS[$i] = int(rand($MAX - $MIN) + $MIN); } return @INTEGERS; } ################################################## # Sorts an array of numbers and overwrites the original array. sub SortNumbers { my @LIST = sort { $a <=> $b } @_; # Sort numbers... for (my $i = 0; $i < @_; $i++) # Modify original array. { $_[$i] = $LIST[$i]; } } ################################################## # Displays the values of an array. sub DisplayList { print "\n\n--- ", (scalar @_), " items ", '-' x 64, "\n\n"; for (my $i = 0; $i < @_; $i++) { print ' ', $_[$i], "\t"; } print '-' x 79, "\n"; } ##################################################