#!/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 displays step by step what we do and how we solve the problem.
# Written by Zsolt Nagy-Perge in Feb 2022 (zsnp@juno.com).
#

use strict;
use warnings;

my $GOAL = 500;

my $ARRAY_SIZE = 100;   # We will use this many random numbers
my $MIN = 40;          # ranging from this
my $MAX = 1000;         # to this.

my @RANDOM_NUMBERS = RandomIntList($ARRAY_SIZE, $MIN, $MAX);

#
# 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
#@RANDOM_NUMBERS = qw(863 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

DisplayList(@RANDOM_NUMBERS);

my $BEST_COMBO = SolveKnapSack($GOAL, @RANDOM_NUMBERS);

my $DIFF = $GOAL - eval($BEST_COMBO);
if ($DIFF > 0)
  { print "\nThat's $DIFF less than our goal $GOAL.\n"; }

exit;

##################################################
#                                       v2022.2.25
# This function takes an array of numbers and
# returns a subset of this array as a string
# which when added up comes out to TOTAL or
# a little bit less than TOTAL.
#
# Usage: STRING = SolveKnapSack(TOTAL, LIST_OF_NUMBERS)
#
sub SolveKnapSack
{
  my $GOAL = shift;
  my @NUMBERS;
  my $ORIGINAL_SIZE = @_;
  my $NEW_SIZE;

  # Create a copy of the input array and also find the MIN and MAX values.
  my ($MIN, $MAX) = (9999999999, -1);
  foreach (@_)
  {
    if ($_ < 1 || $_ > $GOAL) { next; }   # Skip numbers that obviously aren't going to work
    push(@NUMBERS, $_);
    $_ >= $MIN or $MIN = $_;
    $_ <= $MAX or $MAX = $_;
  }
  $NEW_SIZE = @NUMBERS;
  if ($NEW_SIZE < $ORIGINAL_SIZE)
    { print "\nThe set of numbers has been reduced: ", $ORIGINAL_SIZE - $NEW_SIZE, " number(s) have been removed\nfrom the list because they were either too big or too small.\n"; }
  print "\n\tRANGE=($MIN, $MAX)  GOAL=$GOAL\n";

  # If the MAX value equals the number we're seeking, then we have found the solution!
  if ($MAX == $GOAL) { print "\nRESULT: IT'S THE MAX VALUE!\n"; return $MAX; }

  my $STOP_AFTER_ADDING_SMALL_NUMBERS = 0;
  if ($MIN == $MAX)   # Hey, what if all numbers are the same? Lol
  {
    print "\nWe can skip sorting the numbers, because they're all the same!\n";
    $STOP_AFTER_ADDING_SMALL_NUMBERS = 1;
  }
  else
  {
    SortNumbers(@NUMBERS);
    print "\nThe numbers have been sorted! from $MIN to $MAX and our goal is $GOAL.\n";
  }

  #################################################################################
  # FIRST WE WILL JUST ADD UP ALL THE NUMBERS FROM THE LEAST TO THE GREATEST, AND SEE WHAT HAPPENS...

  my $SUM_SO_FAR = $NUMBERS[0];
  my $BEST_COMBO_FROM_SMALL_NUMBERS = $NUMBERS[0];

  my $N = 1;   # Count how many small numbers we can add up
  for (; $N < @NUMBERS; $N++)
  {
    $SUM_SO_FAR += $NUMBERS[$N];
    if ($SUM_SO_FAR <= $GOAL)
    {
      $BEST_COMBO_FROM_SMALL_NUMBERS .= '+' . $NUMBERS[$N];
      print "\nAdding up: $BEST_COMBO_FROM_SMALL_NUMBERS = $SUM_SO_FAR";
      if ($SUM_SO_FAR == $GOAL) { print "\nJust started adding up all the smallest numbers, and look what we got!!!\n$SUM_SO_FAR = $BEST_COMBO_FROM_SMALL_NUMBERS\n"; return $BEST_COMBO_FROM_SMALL_NUMBERS; }
    }
    else { $SUM_SO_FAR = eval($BEST_COMBO_FROM_SMALL_NUMBERS); last; }
  }
  print "\nOk. We just added up the first $N numbers.\n\n";

  if ($STOP_AFTER_ADDING_SMALL_NUMBERS)
  {
    print "\nRESULT: $SUM_SO_FAR     That's all!  Have a nice day! :-)\n\n";
    return $BEST_COMBO_FROM_SMALL_NUMBERS;
  }

  # Any combination of numbers will have to get us closer to our goal.
  # If not, then we fall back to the $FINAL_COMBO value:
  my $BEST_COMBO_SO_FAR = ($SUM_SO_FAR > $MAX) ? $BEST_COMBO_FROM_SMALL_NUMBERS : $MAX;
  my $FINAL_COMBO = $BEST_COMBO_SO_FAR;

  #################################################################################
  # NOW, WE WILL ADD UP PAIRS OF NUMBERS STARTING WITH THE LARGEST FIRST
  for (my $i = $#NUMBERS; $i > 0; $i--)    # Go down the list starting with the largest numbers...
  {
    my $TEST = $NUMBERS[$i] + $NUMBERS[$i-1];     # Add up the largest + the next largest number, and see what we get...
    my $CURRENT_COMBO = $NUMBERS[$i] . '+' . $NUMBERS[$i-1]; 
    # If $TEST is still larger, then keep going down to the next smaller value.
    # If $TEST is smaller, then try to pack as many large values as possible.
    if ($TEST <= $GOAL)
    {
      $BEST_COMBO_SO_FAR = $NUMBERS[$i] . '+' . $NUMBERS[$i-1];

### DEBUGGING:
      print "\nLevel 1 Testing: $BEST_COMBO_SO_FAR = ", eval($BEST_COMBO_SO_FAR);

      if ($TEST == $GOAL) { print "\nRESULT: $TEST = ($BEST_COMBO_SO_FAR)  YES!!!\n"; return $BEST_COMBO_SO_FAR; }

      # I guess, this is called the "greedy" method.
      # ADD UP ALL BIG NUMBERS FROM NOW ON UNTIL WE FIND THE CLOSEST NUMBER.
      my $BEST_COMBO_2 = $BEST_COMBO_SO_FAR;
      for (my $j = $i - 2; $j >= 0; $j--)
      {
        $TEST += $NUMBERS[$j];
        if ($TEST <= $GOAL)
        {
          $BEST_COMBO_2 .= '+' . $NUMBERS[$j];   # Save this as best

### DEBUGGING:
          print "\nLevel 2 Testing: $BEST_COMBO_2 = ", eval($BEST_COMBO_2);

          if ($TEST == $GOAL) { print "\nRESULT: $TEST = ($BEST_COMBO_2)  YES!!!\n"; return $BEST_COMBO_2; }
        }
        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.
          $TEST = eval($BEST_COMBO_2);
          for (my $k = 0; $k < $j; $k++)
          {
            $TEST += $NUMBERS[$k];
            if ($TEST <= $GOAL)
            {
              $BEST_COMBO_2 .= '+' . $NUMBERS[$k];   # Save this as best
              if ($TEST > $GOAL) { last; }  # $BEST_COMBO_2 has our best solution.

### DEBUGGING:
          print "\nLevel 3 Testing: $BEST_COMBO_2 = $TEST";

              if ($TEST == $GOAL) { print "\nWHEW!!! We did it!!!\nRESULT: $TEST = $BEST_COMBO_2\n\n"; return $BEST_COMBO_2; }
            }
          }
          last;
        }
      }
      if (eval($BEST_COMBO_SO_FAR) < eval($BEST_COMBO_2)) { $BEST_COMBO_SO_FAR = $BEST_COMBO_2; }   # We have made some improvements!
      if (eval($BEST_COMBO_SO_FAR) < $MAX) { $BEST_COMBO_SO_FAR = $MAX; }                           # Nah, all of our effort was in vain! :(
      if (eval($BEST_COMBO_SO_FAR) > eval($FINAL_COMBO)) { $FINAL_COMBO = $BEST_COMBO_SO_FAR; }
             # GREEDY METHOD HAS BEEN TRIED FROM THIS NUMBER GOING DOWN.
             # NOW, THE LOOP WILL CONTINUE WITH A SLIGHTLY LESS GREEDY APPROACH.
    }    
  }

  print "\n\nAfter doing a lot of hard work, here's the best we can do:\n$FINAL_COMBO = ", eval($FINAL_COMBO), "\n\n";
  return $FINAL_COMBO;
}
##################################################
#                                       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 "\n\n", '-' x 79, "\n";
}
##################################################