求解不等式算法

jzp520520

我需要解决一个线材切割问题，例如一根钢材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

表述为数学形式就是，10-（2.5a+2.6b+1.9c）<1.9；10-（2.5a+2.6b+1.9c）>=0；a,b,c=0,1,2,3....。
我想要写一个程序，求出这种算法的所有方案，即a,b,c的所有组合。实际使用中，可能不止三种尺寸，视输入而定。输出格式类似于表格，也可以转置成纵向表格，这样方便输出。求大侠给些编程思路。

yestreenstars

实际使用中，可能不止三种尺寸，视输入而定。

这是难点，尺寸的数目决定循环的个数。

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;
    

复制代码

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
    

复制代码

cujeson

回复 3# rubyish


    大神，完全看不懂啊！有空能否给小白解析一下（主要第7行及以后的不懂）？你写的代码实在太高深了

jzp520520

谢谢！没读大骆驼，完全看不懂，只能惊呼大神了！

rubyish

回复 4# cujeson

line 8: recursive cartesian product sub, 只可意会，不可以言传也。
千言万语，都不能说清楚了。
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

复制代码

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. }

复制代码

try2_oneline = try2

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

复制代码

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

复制代码

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;

复制代码

• @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

复制代码

104359176

切割算法是一种非常有用的算法, 可广泛用于板材切割,钢结构制作领域,三维的堆积算法,可用于货物装箱,集装箱配载领域.

通常是给定一个面积或体积,按照一个原则,计算出空间利用率最高的方案.

希望大家都来尝试一下这个算法.我曾经做过这个算法,但比较复杂.

这个算法如果证明效率高, 正确,可以成为了一个有用的产品项目.

yestreenstars

回复 7# 104359176
那你评价一下rubyish的那个算法如何？

   

cujeson

回复 6# rubyish


    无论如何，先感谢再拜读

jzp520520

回复 6# rubyish


    解释的好详细，我还有一点不明白，@$_这是什么意思？形似数组引用，但好像不是的。谢谢大神细心解答！