一道应用题,大家有兴趣看下,不知道做得对不对?
本人才疏学浅,不知道这题做对不对,大家来帮忙看下!一．
已知：
$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
/**
* 已知条件：$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=($ax+$c+$d)*($by+$c+$e)
* 即：FG的面积为：S >= m*S
* 代入数得：
* 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大于m*S,<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等于m*S,<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();
*/
?>
顶楼主的钻研精神！ 呵呵，这更像是在钻研算法问题，总得来说，楼主提供的算法类似于初步贪婪算法，这样的算法是得不到很良好的结果，且计算效率也不高，如果是出于解答应用题，按照习惯的逻辑以及懒惰程度，我100%的肯定也会首先考虑这样的方式。不过如果我们出于研究、学习的目的，那么想这种空间利用率的算法，公认最优秀的算法包括了“启发式算法”，以及更加科学的“模拟退火遗传算法”，启发式算法的空间利用率在88%左右，退火遗传算法能够有效的达到93%，当然这是通过老生常谈的集装箱问题得出的数据，相比之下，2维的这到题也同样可以应用此原理来解决。
为楼主的研究精神表示崇拜，这种问题涉及到实际生产，直接影响生本，估计有高人也只能给看看写的对不对了……希望大家多说说，搬板凳来学习中 我是纯学习的，楼上说的也是头头是道，呵呵。 3楼兄弟，
说得不错，这算法确实没有什么好效率，所以现在需要大家来帮忙，给一种好的算法，
而且得到最大的利用率。
这道题我是在匆忙中完成的，没有去考虑效率问题。。
你说的“启发式算法”，“模拟退火遗传算法”，这些算法，能否给出一点代码来，或者算术表达式来，小弟在此等待。。。。
希望大家都来讨论下。。。。 没人来看,自己来顶下..
期待大家的最佳算法呢 菜鸟帮顶
页:
[1]