题目大意:从给定各种价值和体积的物品中选取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
阅读(1519) | 评论(0) | 转发(1) |