求解不等式算法

rubyish

回復(fù) 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;

復(fù)制代碼

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;

復(fù)制代碼

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;

復(fù)制代碼

rubyish

回復(fù) 7# 104359176


    大牛，有 any 調(diào)優(yōu) de idea?.

rubyish

回復(fù) 10# jzp520520

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

復(fù)制代碼

大眾推薦

看不懂。。。但是感覺蠻高深的

rubyish 發(fā)表于 2013-11-29 00:30
No Optimization!
看看:

rubyish

回復(fù) 14# 大眾推薦

大牛，有 any 調(diào)優(yōu) de idea?.
   

cujeson

回復(fù) 3# rubyish


大神，請教一下這行代碼：
@_ ? map { my $h = $_; map [ $h, @$_ ], try(@_) } @{ +shift } : [];
以下是我的疑問：
1.第一個黃色區(qū)域@_判斷的是什么？數(shù)組長度？數(shù)組是否存在？數(shù)組是否為空？
2.第二個黃色區(qū)域map [ $h, @$_ ], try(@_)，這嵌套看起來有點暈，這map函數(shù)返回值是什么�。�
3.第二個黃色區(qū)域@{ +shift }這是從@_的左邊取出一個元素來創(chuàng)建數(shù)組的意思嗎？
4.第三個黃色區(qū)域[]表示什么？
5.還有一個問題就是下面也出現(xiàn)一個類似的()，這是返回空列表的意思嗎？

問題比較多，感謝大神不吝賜教！

rubyish

回復(fù) 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/];

復(fù)制代碼

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
    

復(fù)制代碼

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]

大眾推薦

親，我是真心看不懂并真心認(rèn)為很高深，反正我看到帶@ $ 等編程，包括shell，就頭暈，就真心覺得你們牛X，因為我覺得精神稍微不集中，就會犯錯。。。

rubyish 發(fā)表于 2013-12-01 23:25
回復(fù) 14# 大眾推薦

大牛，有 any 調(diào)優(yōu) de idea?.

kggg

回復(fù) 17# rubyish


return [] 是不是相當(dāng)于return undef;


   

jason680

回復(fù) 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

復(fù)制代碼

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