Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1003619
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: Python/Ruby

2012-04-16 19:10:30

 
题目大意:从给定各种价值和体积的物品中选取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;

点击(此处)折叠或打开

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

  4. #volumn restriction is 14
  5. my $maxSize = 14;

  6. #count restriction is 4
  7. my $maxCount = 4;

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

  10. #get the best choice from %hash by volumn restrict $max
  11. sub BestChoice{
  12.     my $matchk = -1;
  13.     my $tmp = 0;
  14.     while(my ($k, $v) = each(%bones)){
  15.         if($v>$tmp and $k<= $maxSize-GetVolumns(@_) and !($k~~@_) ){
  16.             $matchk = $k;
  17.         }
  18.     }
  19.     return $matchk;
  20. }

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

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


 

 

阅读(1519) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~