求解不等式算法

jzp520520

我需要解決一個(gè)線材切割問(wèn)題，例如一根鋼材10m，我要切割2.5m，2.6m，1.9m三種尺寸，剩下的廢料要小于最小的尺寸。有以下11種切割方案。
        x1        x2        x3        x4        x5        x6        x7        x8        x9        x10        x11
2.5        4        3        2        2        1        1        1        0        0        0        0
2.6        0        0        1        0        2        0        1        3        2        1        0
1.9        0        1        1        2        1        3        2        1        2        3        5
sum        10        9.4        9.5        8.8        9.6        8.2        8.9        9.7        9        8.3        9.5
remain        0        0.6        0.5        1.2        0.4        1.8        1.1        0.3        1        1.7        0.5

表述為數(shù)學(xué)形式就是，10-（2.5a+2.6b+1.9c）<1.9；10-（2.5a+2.6b+1.9c）>=0；a,b,c=0,1,2,3....。
我想要寫一個(gè)程序，求出這種算法的所有方案，即a,b,c的所有組合。實(shí)際使用中，可能不止三種尺寸，視輸入而定。輸出格式類似于表格，也可以轉(zhuǎn)置成縱向表格，這樣方便輸出。求大俠給些編程思路。

yestreenstars

實(shí)際使用中，可能不止三種尺寸，視輸入而定。

這是難點(diǎn)，尺寸的數(shù)目決定循環(huán)的個(gè)數(shù)。

rubyish

No Optimization!
看看:

1. #!/usr/bin/perl
   
2. my $length = 10;
   
3. my @cut = qw/2.5 2.6 1.9/;
   
4. @cut = sort { $b <=> $a } @cut;
   
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 ) = $_;
    
15.     $sum += $cut[$_] * $gimme->[$_] for 0 .. $#{$gimme};
    
16.     $max < $sum && $sum <= $length
    
17.       ? [ sprintf( "%.1f", $sum ), sprintf( "%.2f", $length - $sum ), @$gimme ]
    
18.       : ()
    
19.   } try map [ 0 .. $length / $_ ], @cut;
    

復(fù)制代碼

1.      sum        rem     2.6     2.5     1.9
   
2. 001| 10.0       0.00    0       4       0
   
3. 002| 9.7        0.30    3       0       1
   
4. 003| 9.6        0.40    2       1       1
   
5. 004| 9.5        0.50    0       0       5
   
6. 005| 9.5        0.50    1       2       1
   
7. 006| 9.4        0.60    0       3       1
   
8. 007| 9.0        1.00    2       0       2
   
9. 008| 8.9        1.10    1       1       2
   
10. 009| 8.8        1.20    0       2       2
    
11. 010| 8.3        1.70    1       0       3
    
12. 011| 8.2        1.80    0       1       3
    

復(fù)制代碼

cujeson

回復(fù) 3# rubyish


    大神，完全看不懂��！有空能否給小白解析一下（主要第7行及以后的不懂）？你寫的代碼實(shí)在太高深了

jzp520520

謝謝！沒(méi)讀大駱駝，完全看不懂，只能驚呼大神了！

rubyish

回復(fù) 4# cujeson

line 8: recursive cartesian product sub, 只可意會(huì)，不可以言傳也。
千言萬(wàn)語(yǔ)，都不能說(shuō)清楚了。
http://tv.sohu.com/20130711/n381345559.shtml

usage:

1. my @a = try [ 1, 2 ], [ 'a', 'b' ], [ 'A', 'B' ];
   
2. say join ' | ', map "@$_", @a;
   
3. # 1 a A | 1 a B | 1 b A | 1 b B | 2 a A | 2 a B | 2 b A | 2 b B

復(fù)制代碼

a simple version: try2
perldoc -f glob

1. sub try2 {
   
2.     my ( $head, $tail ) = qw[{ }];
   
3.     my @param = @_;
   
4.     my @body  = map { join( '|,', @$_) .'|' } @param;
   
5.     my $body  = join '}{', @body;
   
6.     my @all   = glob $head . $body . $tail;
   
7.     my @ret   = map { [ split /\|/, $_ ] } @all;
   
8.     return @ret;
   
9. }

復(fù)制代碼

try2_oneline = try2

1. sub try2_oneline {
   
2.     map [ split /\|/ ], glob '{' . join( '}{', map join( '|,', @$_ ) . '|', @_ ) . '}';
   
3. }

復(fù)制代碼

line 12-19: 句型 print ... for @A

• @A: 句型 sort {...} @B
• @B: 句型 map {...} @C
• @C: 句型 try @D
• @D: 句型 map {...} @cut
  

line 12-19 =

1. print ... for sort {...} map {...} try map {...} @cut

復(fù)制代碼

EQV

1. my @D = map {...} @cut;
   
2. my @C = try @D;
   
3. my @B = map {...} @C;
   
4. my @A = sort {...} @B;
   
5. 
   
6. print ... for @A;

復(fù)制代碼

• @D: [ 0, 1, 2, 3, 4 ], [ 0, 1, 2, 3 ], [ 0, 1, 2, 3, 4, 5 ]
• @C: [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 0, 2 ] ...  [ 4, 3, 5 ]
• @B: [ 9.5, 0.50, 0, 0, 5 ], [ 8.3, 1.70, 0, 1, 3 ] ...  [ 10, 0.00, 4, 0, 0 ]
• @A: [ 10, 0.00, 4, 0, 0 ], [ 9.7, 0.30, 0, 3, 1 ] ...  [ 8.2, 1.80, 1, 0, 3 ]
  

line15: sum = 2.5 * a + 2.6 * b + 1.9 * c ....

line 17-18: true ? A : B

1. my @even = map {  $_ % 2 == 0 ? "E$_" : () } 1 .. 10;
   
2. my @eve2 = map { "E$_" } grep { $_ % 2 == 0 } 1 .. 10;
   
3. 
   
4. say join '|', @even;
   
5. # E2|E4|E6|E8|E10
   
6. 
   
7. say join '|', @eve2;
   
8. # E2|E4|E6|E8|E10

復(fù)制代碼

104359176

切割算法是一種非常有用的算法, 可廣泛用于板材切割,鋼結(jié)構(gòu)制作領(lǐng)域,三維的堆積算法,可用于貨物裝箱,集裝箱配載領(lǐng)域.

通常是給定一個(gè)面積或體積,按照一個(gè)原則,計(jì)算出空間利用率最高的方案.

希望大家都來(lái)嘗試一下這個(gè)算法.我曾經(jīng)做過(guò)這個(gè)算法,但比較復(fù)雜.

這個(gè)算法如果證明效率高, 正確,可以成為了一個(gè)有用的產(chǎn)品項(xiàng)目.

yestreenstars

回復(fù) 7# 104359176
那你評(píng)價(jià)一下rubyish的那個(gè)算法如何？

   

cujeson

回復(fù) 6# rubyish


    無(wú)論如何，先感謝再拜讀

jzp520520

回復(fù) 6# rubyish


    解釋的好詳細(xì)，我還有一點(diǎn)不明白，@$_這是什么意思？形似數(shù)組引用，但好像不是的。謝謝大神細(xì)心解答！