fork download
copy 
  1. #!/usr/bin/perl
  2. # your code goes here
  3. sub knapsack 
  4. {  
  5.     my @num_arr = (2);
  6.     my $len = @num_arr;
  7.     my $sum=0;
  8.     foreach my $a (@num_arr)
  9.     {   
  10.         $sum+=$a;
  11.     }   
  12.     my $half_sum = int($sum/2);
  13. 	my @state;
  14.     my @dp =(0)*10000;
  15.     for (my $i=0; $i<$len; $i++)
  16.     {   
  17.         for (my $j=$half_sum; $j >= $num_arr[$i]; $j--)
  18.         {   
  19.             if ($dp[$j] <$dp[$j-$num_arr[$i]] + $num_arr[$i])
  20.             {   
  21.                 $dp[$j] = $dp[$j-$num_arr[$i]] + $num_arr[$i];
  22.         		$state[$i][$j]=1;
  23.             }   
  24.         }   
  25.     }   
  26.     my $gap = $sum - $dp[int($sum/2)] * 2;
  27.     print("array sum is $sum\n");
  28.     print("gap between two part is $gap\n");
  29.  
  30.     my $i = $len; 
  31.     my $j = $half_sum;
  32.     my $left_part_sum = 0;
  33.     my $right_part_sum = 0;
  34.     while ($i--)
  35.     {   
  36.         if ($state[$i][$j]==1)
  37.         {   
  38.             $j -= $num_arr[$i];
  39.             $left_part_sum += $num_arr[$i];
  40.             print("left part num: $num_arr[$i]\n");
  41.         }   
  42.         else
  43.         {
  44.         	 $right_part_sum += $num_arr[$i];
  45.         	print("                    right part num: $num_arr[$i]\n");
  46.         }
  47.     }   
  48.     print("left part sum: $left_part_sum");
  49. 	print("   right part sum: $right_part_sum\n");
  50. }
  51. knapsack();
  52.  
Success #stdin #stdout 0s 17488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
array sum is 2
gap between two part is 2
                    right part num: 2
left part sum: 0   right part sum: 2
https://ideone.com/Sp09vX
language:
Perl (perl 5.28.1)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!