葡萄娱乐官方记壹道并非思路的算法题,将数字金额转换来大写金额

近些年在看有个别PHP算法题,蒙受一个将数字金额转换来大写金额的小算法题,那里贴出本人的二个例证。

今日贤内给了自笔者1道很实在的算法题,把本人绝望难住了,实在想不出去,于是写此博文以记之。

注:那些小算法适用于十万以内的金额。

背景是这么的,以后有二个付款明细的Excel,里面有为哪个发票,哪个集团应付多少钱的鬼斧神工,明细数据是6二条,今后了然大家已经付出的金额为Sum,请问到底怎样发票是已给付的。

<?php
//$num = 12345.67; 
function RMB_Upper($num)
{
    $num = round($num,2);  //取两位小数
    $num = ''.$num;  //转换成数字
    $arr = explode('.',$num);  

    $str_left = $arr[0]; // 12345
    $str_right = $arr[1]; // 67

    $len_left = strlen($str_left); //小数点左边的长度
    $len_right = strlen($str_right); //小数点右边的长度

    //循环将字符串转换成数组,
    for($i=0;$i<$len_left;$i++)
    {
        $arr_left[] = substr($str_left,$i,1);
    }
    //print_r($arr_left);
    //output:Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 )

    for($i=0;$i<$len_right;$i++)
    {
        $arr_right[] = substr($str_right,$i,1);
    }
    //print_r($arr_right);
    //output:Array ( [0] => 6 [1] => 7 )

    //构造数组$daxie
    $daxie = array(
        '0'=>'零',
        '1'=>'壹',
        '2'=>'贰',
        '3'=>'叁',
        '4'=>'肆',
        '5'=>'伍',
        '6'=>'陆',
        '7'=>'柒',
        '8'=>'捌',
        '9'=>'玖',
    );

    //循环将数组$arr_left中的值替换成大写
    foreach($arr_left as $k => $v)
    {
        $arr_left[$k] = $daxie[$v];
        switch($len_left--)
        {
            //数值后面追加金额单位
            case 5:
                $arr_left[$k] .= '万';break;
            case 4:
                $arr_left[$k] .= '千';break;
            case 3:
                $arr_left[$k] .= '百';break;
            case 2:
                $arr_left[$k] .= '十';break;
            default:
                $arr_left[$k] .= '元';break;
        }
    }
    //print_r($arr_left);
    //output :Array ( [0] => 壹万 [1] => 贰千 [2] => 叁百 [3] => 肆十 [4] => 伍元 )

    foreach($arr_right as $k =>$v)
    {
        $arr_right[$k] = $daxie[$v];
        switch($len_right--)
        {
            case 2:
                $arr_right[$k] .= '角';break;
            default:
                $arr_right[$k] .= '分';break;
        }
    }
    //print_r($arr_right);
    //output :Array ( [0] => 陆角 [1] => 柒分 )

    //将数组转换成字符串,并拼接在一起
    $new_left_str = implode('',$arr_left);
    $new_right_str = implode('',$arr_right);

    $new_str = $new_left_str.$new_right_str;

    //echo $new_str;
    //output :'壹万贰千叁百肆十伍元陆角柒分'

    //如果金额中带有0,大写的字符串中将会带有'零千零百零十',这样的字符串,需要替换掉
    $new_str = str_replace('零万','零',$new_str);
    $new_str = str_replace('零千','零',$new_str);
    $new_str = str_replace('零百','零',$new_str);
    $new_str = str_replace('零十','零',$new_str);
    $new_str = str_replace('零零零','零',$new_str);
    $new_str = str_replace('零零','零',$new_str);
    $new_str = str_replace('零元','元',$new_str);


    //echo'<br/>';
    return $new_str;
}


echo RMB_Upper(12345.67);

那是6二条明细数据:

 

653165.00
356029.11
220896.45
146362.00
1847670.00
3018518.91
1347553.07
145010.74
339784.84
199350.28
1206114.00
882000.00
253246.13
720000.00
24194.07
1518952.00
139453.48
200415.00
812044.00
9032764.57
3960608.05
1855126.31
7409087.18
608094.66
225519.59
627912.23
109897.52
1215819.87
4220245.50
94299.00
96547.00
92616.01
597100.54
880440.00
343991.59
70468.19
1092418.47
66911.94
80138.65
1398551.14
172287.48
691097.86
2371693.44
3773148.63
83898.33
89922.75
2619220.46
1179477.63
3440250.98
700000.00
997545.00
272523.00
3009976.00
451891.44
2111314.00
306377.00
142329.00
2057178.00
9340.00
249027.00
60811.50
51188.50

给付的金额为:

35857936.42

这听起来是3个很简短的算法题,其实正是算组合嘛,把各种组成的金额进行相加,借使等于Sum金额,那么就输出那种结合。于是网上找找组合函数的代码,不慢就写出了这一个程序。而且动用了有的简短的测试程序,确认计算是不利的。可是的确用到这些业务中,却夭亡了,总计量太大,根本算不出去。

细心一想,对于每个数字,要么出现,要么不出新,那么其计算复杂度正是O(二^n),那里n=6二,那么基本上就得总计2的614遍,遍历每壹种组成,才能找到任何答案。天啊!二的陆十七次方!

自古以来不恐怕做到啊。想了又想,怎么都并未有想到好的格局把复杂度降下来,难熬。不知晓有未有大神可以化解这一个题材。

那还只是一回数据,现在大概还有100条明细,200条明细的,就这破算法,这更是天文数字,怎么大概算得出来啊?!

 附上现有的代码葡萄娱乐官方,下载

 

更新:

好吧,看来作者太无知了,那几个题材是未有化解办法的,StackOverflow的研究:http://stackoverflow.com/questions/4355955/subset-sum-algorithm

同时还有特别的维基百科页面:http://en.wikipedia.org/wiki/Subset\_sum\_problem\#Pseudo-polynomial\_time\_dynamic\_programming\_solution