钞票找零-贪心,动态规划算法-仙士可博客,技术博客,php,mysql,swoole,php博客
钞票找零问题是一个非常古老的问题,百度那些都有,本文将一步步的讲解关于钞票找零的算法以及优化过程.
贪心算法
假设有1,2,5,10面值的钞票,现在需要找零89元,我们该怎么做呢?
解析一:
这里面,最简单的一种方法,也就是89/1=89 了,我们只需要89张1元面值的即可,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
<?php
class Change
{
protected $moneyArr = [1, 2, 5, 10];`//零钱`
protected $changeMethod`;`//找零方法
public function __construct(`$moneyArr = null)`
{
$moneyArr == null || (`$this->moneyArr = $moneyArr`);
sort(`$this->moneyArr);//顺序排序零钱`
}
public function change(`$moneyNum`)
{
$moneyArr = `$this`->moneyArr;
$changeMethod = [];
while (`$faceValue = array_shift($moneyArr)) {`//从小到大
if (`$faceValue <= $moneyNum) {`//面值必须小于等于找零金额
$quotient = `floor($moneyNum / $faceValue);`//做除数运算
$moneyNum -= `intval($quotient * $faceValue);`//减去已经找过的
if (isset(`$changeMethod[$faceValue`])) {
$changeMethod`[$faceValue] += $quotient;`
} `else {`
$changeMethod`[$faceValue] = $quotient;`
}
}
if (`$moneyNum == 0) {`
break`;`
}
}
if (`$moneyNum`>0){
return null;
}
$this`->changeMethod = $changeMethod;`
return $this`->changeMethod;`
}
}
$change = `new Change([ 2, 5, 10]);`
var_dump(`$change`->change(89));
//
这时候有个问题就是,都是按照最小面值找的,找零89块钱,竟然需要89张1元的纸币,那能不能在能找零的情况,尽可能的将找的纸币数量缩小呢?
这时候我们就需要用到贪心算法
贪心算法是指,在每一次情况下,都选择当前最优的解进行处理,
在这个场景里面,最优的解就应该是从大到小进行找零了,89块钱,先找最大面值的50块钱,然后找10块钱的,以此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<?php
class Change
{
protected $moneyArr = [1, 2, 5, 10];`//零钱`
protected $changeMethod`;`//找零方法
public function __construct(`$moneyArr = null)`
{
$moneyArr == null || (`$this->moneyArr = $moneyArr`);
rsort(`$this->moneyArr);//倒序排序零钱`
}
public function change(`$moneyNum`)
{
$moneyArr = `$this`->moneyArr;
$changeMethod = [];
while (`$faceValue = array_shift($moneyArr)) {`//从小到大
if (`$faceValue <= $moneyNum) {`//面值必须小于等于找零金额
$quotient = `floor($moneyNum / $faceValue);`//做除数运算
$moneyNum -= `intval($quotient * $faceValue);`//减去已经找过的
if (isset(`$changeMethod[$faceValue`])) {
$changeMethod`[$faceValue] += $quotient;`
} `else {`
$changeMethod`[$faceValue] = $quotient;`
}
}
if (`$moneyNum == 0) {`
break`;`
}
}
if (`$moneyNum`>0){
return null;
}
$this`->changeMethod = $changeMethod;`
return $this`->changeMethod;`
}
}
$change = `new Change([1, 2, 5, 10]);`
var_dump(`$change`->change(89));
var_dump(`$change`->change(89));
//array(3) {
[10]=>
float(8)
[5]=>
float(1)
[2]=>
float(2)
}
这样就可以在尽可能纸币数量小的时候找零了
动态规划
=======
在上面的从大到小进行做除数运算,获得一个找零解之后,我们现在研究另一个问题:
当钞票金额只有3,5,需要找零11元时,你会发现上面的算法根本算不出结果,因为它不管从大到小进行除数找零,还是从小到大进行除数找零都不能找到结果(11-3*3=2,11-2*5=1),但其实11元是有解的(2*3+5)
这时候,我们需要在贪心算法的基础上,进行相应的规划(当每次找一个最优解时,尝试通过该解之后继续寻找,但是找零方法只记录到缓存中,如果尝试找零成功,则记录,尝试找零失败,则放弃这个最优解):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
<?php
class Change
{
protected $moneyArr = [1, 2, 5, 10];`//零钱`
protected $changeMethod`;`//找零方法
public function __construct(`$moneyArr = null)`
{
$moneyArr == null || (`$this->moneyArr = $moneyArr`);
rsort(`$this->moneyArr);//倒序排序零钱`
}
public function change(int `$moneyNum,?array $moneyArr`=null)
{
if (`$moneyArr`===null){
$moneyArr =`$this`->moneyArr;
}
$changeMethod = [];
while (`$faceValue = array_shift($moneyArr)) {`//从大到小
if (`$faceValue <= $moneyNum) {`//面值必须小于等于找零金额
$quotient = `floor($moneyNum / $faceValue);`//做除数运算,这里有着最大面值的解,但是因为规划问题,如果$quotient过大可能会造成无解,所以当无解的时候,尝试降低数量
for (`$i = $quotient; $i` `> 0; $i`--) {
$changeMethodTemp = [];`//找零方法缓存`
$moneyNumTemp`=$moneyNum;`//金额缓存
$moneyNumTemp -= `intval($i * $faceValue);`//减去已经找过的
if (isset(`$changeMethodTemp[$faceValue`])) {
$changeMethodTemp`[$faceValue] += $i;`
} `else {`
$changeMethodTemp`[$faceValue] = $i;`
}
//如果当前没有找清,则尝试判断剩余情况是否能找清
if (`$moneyNumTemp == 0){`
$moneyNum = 0;
$changeMethod = `$changeMethodTemp`;
break 2;
}`elseif($moneyNumTemp > 0) {`
$changeMethodTemp2 = `$this->change($moneyNumTemp,$moneyArr );`
if (`$changeMethodTemp2 === null) {`
continue`;`
}
// 有值代表能找清
$moneyNum = 0;
$changeMethod = `$changeMethodTemp + $changeMethodTemp2;`
break 2;
}
}
}
}
if (`$moneyNum > 0) {`
return null;
}
$this`->changeMethod = $changeMethod;`
return $this`->changeMethod;`
}
}
$change = `new Change([3, 5]);`
var_dump(`$change`->change(11));
上面的算法步骤如下:
1:从大到小取出 面值
2:根据最大的做除数运算,获取到当前面值faceValue最多可以找quotient张,
3:根据quotient做循环操作,尝试quotient是否存在找零成功的解,如果存在则直接返回
4:如果quotient不存在找零成功,则继续尝试找quotient-1,以此类推,知道quotient等于0,则代表该面值不能找零成功
5:将面值改为第二大,继续2,3,4操作
加强版动态规划找最优解
通过上面的算法,我们实现了简单的动态规划
使其在面额为3,5,找零11元的情况下,被金额5"贪心迷惑",找2个金额5,导致算法无解
这个算法实现了在这种情况下,不贪心,不被眼前的2*5迷惑,为了"大局",舍弃了表面的最优
那么?这是最优解吗?
当面额只有1,30,50,找零90的情况下,根据贪心+规划算法,我们能得到50*1+30*1+1*10的情况,这需要用到12张钞票,但是实际情况我们只需要找30*3,3张钞票即可解决该问题.这代表着我们需要完全遍历所有能找零的方法,然后根据钞票张数不同进行选择最优解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
<?php
class Change
{
protected $moneyArr = [1, 2, 5, 10];`//零钱`
protected $changeMethod`;`//找零方法
public function __construct(`$moneyArr = null)`
{
$moneyArr == null || (`$this->moneyArr = $moneyArr`);
rsort(`$this->moneyArr);//倒序排序零钱`
}
public function change(int `$moneyNum,?array $moneyArr`=null)
{
if (`$moneyArr`===null){
$moneyArr =`$this`->moneyArr;
}
$optimalChangeMethod = [];`//当前最优方法`
$optimalNum = -1;`//当前最优张数`
while (`$faceValue = array_shift($moneyArr)) {`//从大到小
if (`$faceValue <= $moneyNum) {`//面值必须小于等于找零金额
$quotient = `floor($moneyNum / $faceValue);`//做除数运算,这里有着最大面值的解,但是因为规划问题,如果$quotient过大可能会造成无解,所以当无解的时候,尝试降低数量
for (`$i = $quotient; $i` `> 0; $i`--) {
$changeMethodTemp = [];`//找零方法缓存`
$moneyNumTemp`=$moneyNum;`//金额缓存
$moneyNumTemp -= `intval($i * $faceValue);`//减去已经找过的
if (isset(`$changeMethodTemp[$faceValue`])) {
$changeMethodTemp`[$faceValue] += $i;`
} `else {`
$changeMethodTemp`[$faceValue] = $i;`
}
//如果当前没有找清,则尝试判断剩余情况是否能找清
if (`$moneyNumTemp == 0){`//如果当前情况直接找清,则判断是否优于最优解
$banknoteNum = `array_sum($changeMethodTemp`);
if (`$optimalNum==-1||$banknoteNum<$optimalNum`){
$optimalNum = `$banknoteNum`;
$optimalChangeMethod = `$changeMethodTemp`;
}
}`elseif($moneyNumTemp > 0) {`
$changeMethodTemp2 = `$this->change($moneyNumTemp,$moneyArr`);
if (`$changeMethodTemp2 === null) {`
continue`;`
}
$banknoteNum = `array_sum($changeMethodTemp2)+ array_sum($changeMethodTemp`);
if (`$optimalNum==-1||$banknoteNum<$optimalNum`){
// 有值代表能找清
$optimalNum =`$banknoteNum`;
$optimalChangeMethod = `$changeMethodTemp + $changeMethodTemp2;`
}
}
}
}
}
if (`$optimalNum`==-1){
return null;
}
$this`->changeMethod = $optimalChangeMethod;`
return $this`->changeMethod;`
}
}
$change = `new Change([3,5]);`
var_dump(`$change`->change(11));
本文为仙士可原创文章,转载无需和我联系,但请注明来自仙士可博客www.php20.cn
- 上一篇： 没有了
- 下一篇： phpunit-单元测试神器
Original url: Access
Created at: 2019-04-11 12:09:09
Category: default
Tags: none
未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到
- 上一篇： 主题样式记录
- 下一篇： swoole - lulublog
最新评论