叠放箱子

目前算法复杂度最差情况应该是O(n^3),最好情况O(n^2), 按最好的算法O(n^2)就可以了。 但是改了半天改不出来。    不知道是不是复杂度算错了。

 

有一批编号为1至N且尺寸规格一样的箱子。现在要将其中某些箱子叠放起来，使叠放的高度最大，箱子叠放的规则如下：

    一、每个箱子上最多只能直接叠放一个箱子；

    二、编号较小的箱子不能放在编号较大的箱子之上；

    三、每个箱子都给出了自身重量与可承受重量，每个箱子上的所有箱子重量之和不得超过该箱的可承受重量。

      输入箱子数N（1≤N≤1000）及每个箱子的自身重量与可承受重量，两个数值均为小于等于3000的正整数。

    输出最多可叠放的箱子总数M

 

 

my @data = (
 [19,11],
 [7,6],
 [5,7],
 [6,8],
 [1,2]
);
my @result;
my $max;
for my $i (0 .. @data){
 $result[1][$i] = $data[$i][0];
}
for (my $i = (@data-3); $i>=0; $i--){
 for my $c (2.. @data-$i-1){
  for($i+1 .. @data-$c){
   if(defined($result[$c-1][$_]) and $result[$c-1][$_]<=$data[$i][1]){
    $result[$c][$i] = $data[$i][0]+$result[$c-1][$_];
    $max = $c;
    last;
   }
  }
 }
}
for(@result){
 print "@{$_} \n";
}

print $max;