一道应用题,大家有兴趣看下,不知道做得对不对?

fyp83

本人才疏学浅,不知道这题做对不对,大家来帮忙看下!





一．
已知：

$a=75;


$b=56;

$c=2;

$d=25;


$e=12;

$f=1200;

$g=1000;
其中，$a和$b是小长方形AB的长和宽，$f和$g是大长方形FG的长和宽，工作毛胚为HK, 其他变量之间的关系如下图：
此图中由AB组合成HK的方式为2a2b，其他可能的方式还有1a1b、1a2b、2a1b、1a3b…nanb等
二．请用PHP语言写出FG被m个HK切割后的剩余材料最少（也就是材料利用率最高）的算法。


以下是我的方法:

PHP复制代码

 
<?php
/**
 * 已知条件：$a=75,$b=56,$c=2,$d=25,$e=12,$f=1200,$g=1000
 * 根据图知：$k=2$b+$c+$e,    $h=2$a+$c+$d
 * 求:M个HK切割FG剩余材料最少的算法.
 *
 * 解：设有x个a, y个b, x和y大于0且为整数
 * 那么：HK的面积为：S[hk]=($ax+$c+$d)*($by+$c+$e)
 * 即：FG的面积为：S[fg] >= m*S[hk]
 * 代入数得：
 *         1200000 >= m*(75x+2+25)*(56y+2+12)
 */
class AppMath
{
    var $a=75,$b=56,$c=2,$d=25,$e=12,$f=1200,$g=1000;
    var $Shk;    //HK的面积
    var $Sfg;    //FG的面积
    var $h;        //小矩形的高
    var $k;        //小矩形的宽
    var $x;        //未知数x个a
    var $y;        //未知数y个b
    var $m;        //M个HK切片
    var $xy;    //代数赋值给xy, 控制循环 (x和y的值不会超过FG的积,即:1200000)
   
    function AppMath(){
        $this->m   = 4;    //当M=1,2,3 时
        $this->xy  = 1200000;    //循环赋值代入法     $this->xy = $this->f * $this->g;
        $this->h   = 2*$this->a + $this->c + $this->d;
        $this->k   = 2*$this->b + $this->c + $this->e;
        $this->Shk = ($this->a * $this->x + $this->c + $this->d)*($this->b * $this->y + $this->c + $this->e);
        $this->Sfg = $this->f * $this->g;
    }
 
    function jishuan(){
        echo "<meta http-equiv='Content-Type' content='text/html; charset=utf-8'>"
            ."正在计算中,请耐心等待.......<br>";          
        for($i=1; $i<$this->m; $i++){    //控制M的变数
            for($j=1; $j<$this->xy; $j++){    //控制X的变数
                $this->x = $j;
                for($k=1; $k<$this->xy; $k++){    //控制Y的变数
                    $this->y = $k;
                    //$this->Sfg >= $i * $this->Shk;    //不等式
                    if( $this->Sfg > ($i * $this->Shk) ){    //大于
                        echo "<br>当S[fg]大于m*S[hk],<font color=red>M={$i}</font> 时:<br>";
                        echo "<font color=red>X=</font>".$j."<br>";
                        echo "<font color=red>Y=</font>".$k."<br>";
                    }
                    elseif( $this->Sfg == ($i * $this->Shk) ){    //等于
                        echo "<br>当S[fg]等于m*S[hk],<font color=red>M={$i}</font> 时:<br>";
                        echo "<font color=red>X=</font>".$j."<br>";
                        echo "<font color=red>Y=</font>".$k."<br>";
                    }else{    //小于
                        echo "<br>无小于情况!<br>";
                    }
                }// end Y
            }// end X
        }//end M
    }
}
 
/**
 * 测试:
 * $a = new AppMath;
 * $a->jishuan();
 */
?>
 

复制代码

Hex

顶楼主的钻研精神！

wesleywray

呵呵，这更像是在钻研算法问题，总得来说，楼主提供的算法类似于初步贪婪算法，这样的算法是得不到很良好的结果，且计算效率也不高，如果是出于解答应用题，按照习惯的逻辑以及懒惰程度，我100%的肯定也会首先考虑这样的方式。不过如果我们出于研究、学习的目的，那么想这种空间利用率的算法，公认最优秀的算法包括了“启发式算法”，以及更加科学的“模拟退火遗传算法”，启发式算法的空间利用率在88%左右，退火遗传算法能够有效的达到93%，当然这是通过老生常谈的集装箱问题得出的数据，相比之下，2维的这到题也同样可以应用此原理来解决。

为楼主的研究精神表示崇拜，这种问题涉及到实际生产，直接影响生本，估计有高人也只能给看看写的对不对了……希望大家多说说，搬板凳来学习中

Hex

我是纯学习的，楼上说的也是头头是道，呵呵。

fyp83

3楼兄弟，
说得不错，这算法确实没有什么好效率，所以现在需要大家来帮忙，给一种好的算法，
而且得到最大的利用率。
这道题我是在匆忙中完成的，没有去考虑效率问题。。

你说的“启发式算法”，“模拟退火遗传算法”，这些算法，能否给出一点代码来，或者算术表达式来，小弟在此等待。。。。

希望大家都来讨论下。。。。

fyp83

没人来看,自己来顶下..
期待大家的最佳算法呢

cairunch

菜鸟帮顶