#!/usr/bin/perl
# your code goes here
sub knapsack
{
my @num_arr = (2);
my $len = @num_arr;
my $sum=0;
foreach my $a (@num_arr)
{
$sum+=$a;
}
my $half_sum = int($sum/2); my @state;
my @dp =(0)*10000;
for (my $i=0; $i<$len; $i++)
{
for (my $j=$half_sum; $j >= $num_arr[$i]; $j--)
{
if ($dp[$j] <$dp[$j-$num_arr[$i]] + $num_arr[$i])
{
$dp[$j] = $dp[$j-$num_arr[$i]] + $num_arr[$i];
$state[$i][$j]=1;
}
}
}
my $gap = $sum - $dp[int($sum/2)] * 2; print("array sum is $sum\n"); print("gap between two part is $gap\n");
my $i = $len;
my $j = $half_sum;
my $left_part_sum = 0;
my $right_part_sum = 0;
while ($i--)
{
if ($state[$i][$j]==1)
{
$j -= $num_arr[$i];
$left_part_sum += $num_arr[$i];
print("left part num: $num_arr[$i]\n"); }
else
{
$right_part_sum += $num_arr[$i];
print(" right part num: $num_arr[$i]\n"); }
}
print("left part sum: $left_part_sum"); print(" right part sum: $right_part_sum\n"); }
knapsack();
IyEvdXNyL2Jpbi9wZXJsCiMgeW91ciBjb2RlIGdvZXMgaGVyZQpzdWIga25hcHNhY2sgCnsgIAogICAgbXkgQG51bV9hcnIgPSAoMik7CiAgICBteSAkbGVuID0gQG51bV9hcnI7CiAgICBteSAkc3VtPTA7CiAgICBmb3JlYWNoIG15ICRhIChAbnVtX2FycikKICAgIHsgICAKICAgICAgICAkc3VtKz0kYTsKICAgIH0gICAKICAgIG15ICRoYWxmX3N1bSA9IGludCgkc3VtLzIpOwoJbXkgQHN0YXRlOwogICAgbXkgQGRwID0oMCkqMTAwMDA7CiAgICBmb3IgKG15ICRpPTA7ICRpPCRsZW47ICRpKyspCiAgICB7ICAgCiAgICAgICAgZm9yIChteSAkaj0kaGFsZl9zdW07ICRqID49ICRudW1fYXJyWyRpXTsgJGotLSkKICAgICAgICB7ICAgCiAgICAgICAgICAgIGlmICgkZHBbJGpdIDwkZHBbJGotJG51bV9hcnJbJGldXSArICRudW1fYXJyWyRpXSkKICAgICAgICAgICAgeyAgIAogICAgICAgICAgICAgICAgJGRwWyRqXSA9ICRkcFskai0kbnVtX2FyclskaV1dICsgJG51bV9hcnJbJGldOwogICAgICAgIAkJJHN0YXRlWyRpXVskal09MTsKICAgICAgICAgICAgfSAgIAogICAgICAgIH0gICAKICAgIH0gICAKICAgIG15ICRnYXAgPSAkc3VtIC0gJGRwW2ludCgkc3VtLzIpXSAqIDI7CiAgICBwcmludCgiYXJyYXkgc3VtIGlzICRzdW1cbiIpOwogICAgcHJpbnQoImdhcCBiZXR3ZWVuIHR3byBwYXJ0IGlzICRnYXBcbiIpOwogICAgCiAgICBteSAkaSA9ICRsZW47IAogICAgbXkgJGogPSAkaGFsZl9zdW07CiAgICBteSAkbGVmdF9wYXJ0X3N1bSA9IDA7CiAgICBteSAkcmlnaHRfcGFydF9zdW0gPSAwOwogICAgd2hpbGUgKCRpLS0pCiAgICB7ICAgCiAgICAgICAgaWYgKCRzdGF0ZVskaV1bJGpdPT0xKQogICAgICAgIHsgICAKICAgICAgICAgICAgJGogLT0gJG51bV9hcnJbJGldOwogICAgICAgICAgICAkbGVmdF9wYXJ0X3N1bSArPSAkbnVtX2FyclskaV07CiAgICAgICAgICAgIHByaW50KCJsZWZ0IHBhcnQgbnVtOiAkbnVtX2FyclskaV1cbiIpOwogICAgICAgIH0gICAKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgIAkgJHJpZ2h0X3BhcnRfc3VtICs9ICRudW1fYXJyWyRpXTsKICAgICAgICAJcHJpbnQoIiAgICAgICAgICAgICAgICAgICAgcmlnaHQgcGFydCBudW06ICRudW1fYXJyWyRpXVxuIik7CiAgICAgICAgfQogICAgfSAgIAogICAgcHJpbnQoImxlZnQgcGFydCBzdW06ICRsZWZ0X3BhcnRfc3VtIik7CglwcmludCgiICAgcmlnaHQgcGFydCBzdW06ICRyaWdodF9wYXJ0X3N1bVxuIik7Cn0Ka25hcHNhY2soKTsK