求解不等式算法

rubyish

回复 8# yestreenstars

那个no效率
10种尺寸，要 15 s


try: 12 s

1. #!/usr/bin/perl
   
2. my $length = 10;
   
3. my @cut    = sort { $b <=> $a }
   
4.   qw/2.5 2.6 1.9 3.5 2.0 4.0 4.5 5 4.7 3.2/;
   
5. my ( $max, $count ) = ( $length - $cut[-1], '001' );
   
6. 
   
7. sub try {
   
8.     @_ ? map { my $h = $_; map [ $h, @$_ ], try(@_) } @{ +shift } : [];
   
9. }
   
10. 
    
11. print join( "\t", '     sum', 'rem', @cut ), $/;
    
12. print $count++, '| ', join( "\t", @$_ ), $/
    
13.   for sort { $b->[0] <=> $a->[0] } map {
    
14.     my ( $gimme, $sum, $i ) = $_;
    
15.     for (@$gimme) {
    
16.         $sum += $cut[ $i++ ] * $_;
    
17.         last if $sum > $length;
    
18.     }
    
19.     $max < $sum && $sum <= $length
    
20.       ? [ sprintf( "%.1f", $sum ), sprintf( "%.2f", $length - $sum ), @$gimme ]
    
21.       : ()
    
22.   } try map [ 0 .. $length / $_ ], @cut;

复制代码

try2: 8s

1. #!/usr/bin/perl
   
2. my $length = 10;
   
3. my @cut    = sort { $b <=> $a }
   
4.   qw/2.5 2.6 1.9 3.5 2.0 4.0 4.5 5 4.7 3.2/;
   
5. my ( $max, $count ) = ( $length - $cut[-1], '001' );
   
6. 
   
7. sub try2 {
   
8.     map [ split /\|/ ],
   
9.       glob '{' . join( '}{', map join( '|,', @$_ ) . '|', @_ ) . '}';
   
10. }
    
11. 
    
12. print join( "\t", '     sum', 'rem', @cut ), $/;
    
13. print $count++, '| ', join( "\t", @$_ ), $/
    
14.   for sort { $b->[0] <=> $a->[0] } map {
    
15.     my ( $gimme, $sum, $i ) = $_;
    
16.     for (@$gimme) {
    
17.         $sum += $cut[ $i++ ] * $_;
    
18.         last if $sum > $length;
    
19.     }
    
20.     $max < $sum && $sum <= $length
    
21.       ? [ sprintf( "%.1f", $sum ), sprintf( "%.2f", $length - $sum ), @$gimme ]
    
22.       : ()
    
23.   } try2 map [ 0 .. $length / $_ ], @cut;

复制代码

try3: 8s

1. #!/usr/bin/perl
   
2. my $length = 10;
   
3. my @cut    = sort { $b <=> $a }
   
4.   qw/2.5 2.6 1.9 3.5 2.0 4.0 4.5 5 4.7 3.2/;
   
5. my ( $max, $count, @choice ) = ( $length - $cut[-1], '001' );
   
6. 
   
7. sub try3 {
   
8.     my ( $check, $t, @A ) = ( 1, 1, @_ );
   
9.     my @elem = map { $check *= @$_; scalar @$_ } @A;
   
10.     my @M = reverse 1, map $t = $t * $elem[ -$_ ], 1 .. $#elem;
    
11.     sub {
    
12.         return unless $check--;
    
13.         [ map $A[$_][ $check / $M[$_] % $elem[$_] ], 0 .. $#elem ];
    
14.     };
    
15. }
    
16. 
    
17. my $gimme = try3 map [ 0 .. $length / $_ ], @cut;
    
18. 
    
19. while ( my $try = $gimme->() ) {
    
20.     my ( $sum, $i );
    
21.     for (@$try) {
    
22.         $sum += $cut[ $i++ ] * $_;
    
23.         last if $sum > $length;
    
24.     }
    
25.     next if $sum > $length or $sum <= $max;
    
26.     push @choice,
    
27.       [ sprintf( "%.1f", $sum ), sprintf( "%.2f", $length - $sum ), @$try ];
    
28. }
    
29. 
    
30. print join( "\t", '     sum', 'rem', @cut ), $/;
    
31. print $count++, '| ', join( "\t", @$_ ), $/
    
32.   for sort { $b->[0] <=> $a->[0] } @choice;

复制代码

rubyish

回复 7# 104359176


    大牛，有 any 调优 de idea?.

rubyish

回复 10# jzp520520

1. my $a = [ 1, 2, 3 ];
   
2. my @a = @$a;
   
3. say @a;   # 123

复制代码

大众推荐

看不懂。。。但是感觉蛮高深的

rubyish 发表于 2013-11-29 00:30
No Optimization!
看看:

rubyish

回复 14# 大众推荐

大牛，有 any 调优 de idea?.
   

cujeson

回复 3# rubyish


大神，请教一下这行代码：
@_ ? map { my $h = $_; map [ $h, @$_ ], try(@_) } @{ +shift } : [];
以下是我的疑问：
1.第一个黄色区域@_判断的是什么？数组长度？数组是否存在？数组是否为空？
2.第二个黄色区域map [ $h, @$_ ], try(@_)，这嵌套看起来有点晕，这map函数返回值是什么啊？
3.第二个黄色区域@{ +shift }这是从@_的左边取出一个元素来创建数组的意思吗？
4.第三个黄色区域[]表示什么？
5.还有一个问题就是下面也出现一个类似的()，这是返回空列表的意思吗？

问题比较多，感谢大神不吝赐教！

rubyish

回复 16# cujeson

1. sub try {
   
2.     return [] if @_ == 0;
   
3.     my $a = shift;
   
4.     my @R =
   
5.       map {
   
6.         my $h = $_;
   
7.         print "-> $h ";
   
8.         map { [ $h, @$_ ] } try(@_)
   
9.       } @$a;
   
10.     say "$/\@a = @$a  return =";
    
11.     say "\t@$_ " for @R;
    
12.     @R;
    
13. }
    
14. 
    
15. try [qw/A B/], [qw/x y/], [qw/1 2 3 4/];

复制代码

output:

1. -> A -> x -> 1 -> 2 -> 3 -> 4
   
2. @a = 1 2 3 4  return =
   
3.         1
   
4.         2
   
5.         3
   
6.         4
   
7. -> y -> 1 -> 2 -> 3 -> 4
   
8. @a = 1 2 3 4  return =
   
9.         1
   
10.         2
    
11.         3
    
12.         4
    
13. 
    
14. @a = x y  return =
    
15.         x 1
    
16.         x 2
    
17.         x 3
    
18.         x 4
    
19.         y 1
    
20.         y 2
    
21.         y 3
    
22.         y 4
    
23. -> B -> x -> 1 -> 2 -> 3 -> 4
    
24. @a = 1 2 3 4  return =
    
25.         1
    
26.         2
    
27.         3
    
28.         4
    
29. -> y -> 1 -> 2 -> 3 -> 4
    
30. @a = 1 2 3 4  return =
    
31.         1
    
32.         2
    
33.         3
    
34.         4
    
35. 
    
36. @a = x y  return =
    
37.         x 1
    
38.         x 2
    
39.         x 3
    
40.         x 4
    
41.         y 1
    
42.         y 2
    
43.         y 3
    
44.         y 4
    
45. 
    
46. @a = A B  return =
    
47.         A x 1
    
48.         A x 2
    
49.         A x 3
    
50.         A x 4
    
51.         A y 1
    
52.         A y 2
    
53.         A y 3
    
54.         A y 4
    
55.         B x 1
    
56.         B x 2
    
57.         B x 3
    
58.         B x 4
    
59.         B y 1
    
60.         B y 2
    
61.         B y 3
    
62.         B y 4
    

复制代码

in last element [1, 2, 3, 4]
map { my $h = $_; map [ $h, @$_ ], try(@_) } 1, 2, 3, 4
now @_ is empty so sub return []
[ $h, @$_ ] => [ $h, @{ [] } ] => [ $h ] -> [1]
[1]
[2]
[3]
[4]

in [x, y]
map [ $h, @$_ ], [1], [2], [3], [4]
[ $h, @$_ ] => [ x, @{ [1] } ] =>
[x, 1]
[x, 2]
[x, 3]
[x, 4]
....
[y, 4]

in [A, B]
map [ $h, @$_ ], [x, 1],[x, 2] ... [y, 4]
[ $h, @$_ ] => [ A, @{ [x, 1] } ] =>
[A, x, 1]
[A, x, 2]
...
[A, y, 4]
[B, x, 1]
....
[B, y, 4]

大众推荐

亲，我是真心看不懂并真心认为很高深，反正我看到带@ $ 等编程，包括shell，就头晕，就真心觉得你们牛X，因为我觉得精神稍微不集中，就会犯错。。。

rubyish 发表于 2013-12-01 23:25
回复 14# 大众推荐

大牛，有 any 调优 de idea?.

kggg

回复 17# rubyish


return [] 是不是相当于return undef;


   

jason680

回复 11# rubyish


would you like this

$ cat cut.pl
#!/usr/bin/perl

use strict;
use warnings;

while(<DATA>){
  chomp;
  next if(m/^\s*#/);
  next if(m/^\s*$/);
  
  my($sTotal, @aCut) = split;
  get_cut($sTotal, @aCut);
}

sub get_cut{
  my($sTotal, @aCut) = @_;
  our @aAns = ();
  our $sCnt = 0;
  my $sMin = $aCut[0];
  for(@aCut){$sMin = $_ if($sMin > $_)};

  print "Total Length= $sTotal, Min = $sMin\n";
  printf("%4s","");
  printf(" %5.2f", $_) foreach(@aCut);
  printf(" %5s %5s\n", "Sum", "Rem");

  _cut($sTotal, 0, $sMin, \@aCut, (0) x scalar(@aCut));

  printf("%4s","");
  printf(" %5.2f", $_) foreach(@aCut);
  printf(" %5s %5s\n", "Sum", "Rem");
  print "Total length = $sTotal, Min = $sMin\n";
  print "Total count = $sCnt\n\n";

  sub _cut{
    my($sTotal, $sOffset, $sMin, $raCut, @aNum) = @_;
    my $sSum = 0;
    $sSum += $aNum[$_] * $raCut->[$_]   for (0 .. (scalar @aNum -1));
    my $sDiff = sprintf("%.2f",$sTotal - $sSum);
    return if($sDiff < 0);
    if($sOffset >= scalar @aNum ){
      if(0 <= $sDiff && $sDiff < $sMin){
        printf("x%03d", ++$sCnt);
        printf(" %5d", $_) foreach(@aNum);
        printf(" %5.2f %5.2f\n", $sSum, $sDiff);
            push @aAns, [@aNum];
          }
      return
        }
    foreach (0 .. int($sTotal/$raCut->[$sOffset])){
      $aNum[$sOffset] = $_;
      _cut($sTotal, $sOffset+1, $sMin, $raCut, @aNum);
        }
  }
}

__DATA__
10 2.5 2.6 1.0 1.1
10 2.5 2.6 1.9 3.5 2.0 4.0 4.5 5 4.7 3.2

1. $ time perl cut.pl
   
2. Total Length= 10, Min = 1.9
   
3.       2.50  2.60  1.90  3.50  2.00  4.00  4.50  5.00  4.70  3.20   Sum   Rem
   
4. x001     0     0     0     0     0     0     0     0     0     3  9.60  0.40
   
5. x002     0     0     0     0     0     0     0     0     2     0  9.40  0.60
   
6. ...
   
7. x135     3     0     0     0     1     0     0     0     0     0  9.50  0.50
   
8. x136     3     0     1     0     0     0     0     0     0     0  9.40  0.60
   
9. x137     4     0     0     0     0     0     0     0     0     0 10.00  0.00
   
10.       2.50  2.60  1.90  3.50  2.00  4.00  4.50  5.00  4.70  3.20   Sum   Rem
    
11. Total length = 10, Min = 1.9
    
12. Total count = 137

复制代码

real    0m0.324s
user    0m0.004s
sys    0m0.128s