[ACM] Bone collector(01背包问题)

 

题目大意：从给定各种价值和体积的物品中选取n件，装进容积为v背包。 问最多背包中能装多少价值的东西。
代码中 %bones 保存物品列表， key为物品体积， value为物品价值。

体积限制为14, 数量限制为4

my %bones = (1 => 5, 2=>4, 3 =>3, 4 => 2, 5 =>1, 6=>7, 8=>11);

#volumn restriction is 14

my $maxSize = 14;

#count restriction is 4

my $maxCount = 4;

#input data
#key is the bone's volumn and the value is bone's value
my %bones = (1 => 5, 2=>4, 3 =>3, 4 => 2, 5 =>1, 6=>7, 8=>11);

#volumn restriction is 14
my $maxSize = 14;

#count restriction is 4
my $maxCount = 4;

#hast table to keep result. key is bones' value, and the value is array's ref which stores bones list
my %fbags;

#get the best choice from %hash by volumn restrict $max
sub BestChoice{
    my $matchk = -1;
    my $tmp = 0;
    while(my ($k, $v) = each(%bones)){
        if($v>$tmp and $k<= $maxSize-GetVolumns(@_) and !($k~~@_) ){
            $matchk = $k;
        }
    }
    return $matchk;
}

#abag is ref of selected bones, $ahash is ref of left bones.
sub f{
    my (@bag) = @_;

    #$count: bones amount pending on fill
    my $count = $maxCount - @bag;
    #Tracking the last bone, if the volumn doesn