算法Balabala凑零钱问题理想版

2020-05-03  本文已影响0人  波澜步惊

前言

作为API Call，可以不去学算法，但是高级工程师，不可能对算法一无所知。

上一篇 斐波拉契数列的问题，讲述了动态规划算法的大概套路，这次来一点真正的实战，编程语言依然用kotlin.

前文回顾

上一篇文末说的动态规划基本套路，最重要的，也是第一个步骤 是 写出动态规划"状态转移方程"

这一步骤是和编程语言完全无关的。纯粹的数学理论。

动态规划实战：理想版凑零钱问题

问题抛出

一件商品要18块，但是我只有零钱，1元，2元，5元，假设零钱数目无限多。现在我要知道，我要用零钱买这一件商品，所需的零钱的最少张数是多少。

问题分离

前提

零钱有1元，2元，5元, 并且数量无限多。

目标

求解凑出18元的目标金额所需零钱的最少张数

问题分解

分情况讨论，

看着有点绕，写成“状态转移方程”一眼就能看明白.

image-20200502132911765.png

根据上面的“状态转移方程”，写出伪代码：

  val coins = [1,2,5]// 零钱只提供1,2,5元的，不限数目
  res = Long.maxvalue.// 由于是要取最小值，所以初始化为long的最大值
  f(n) = if(n=0) return 0 (目标金额是0，那就不需要凑，返回0)
         if(n<0) return -1(目标金额是负数，异常情况，返回-1)
         if(n>0) {
            for(i in coins){// 遍历所有零钱 
               res = min(res,1+ f(n-coin)) // 用一张当前零钱面值，加上扣除当前面值之后的金额递归回调
            }
            return res
      }

先不写程序代码，我们来分析一下这种原始解法的复杂度。

这里我们先把零钱数组的size设定为k

时间复杂度:

所以，时间复杂度就是knx2k = O(2kn+1)*

一个指数级别的时间复杂度，一看就有点慎得慌。

空间复杂度：

由于没有数据保存，一律认为空间复杂度是O(1)

暴力解法

OK，思路清楚了，我们开始码代码

import java.lang.Integer.min

val change = arrayOf(1, 2, 5) // 零钱就是1,2,5

var calCount = 0

/**
 * @param targetAmount 要用零钱凑成的目标金额
 */
fun changeMoney(targetAmount: Long): Int {
    var finalCount = Int.MAX_VALUE // 由于要计算出最小值，所以先初始化为最大值
    if (targetAmount == 0L) return 0 // 贼
    if (targetAmount < 0) return -1
    for (c in change) {
        val subRes = changeMoney(targetAmount - c)
        if (subRes == -1) continue
        finalCount = min(finalCount, 1 + subRes)
    }
    calCount++
    return finalCount
}

fun main() {
    val start = System.currentTimeMillis()
    val changeMoney = changeMoney(18)
    println("凑成目标金额所需的最小零钱数：$changeMoney , 子问题总数是${calCount}")
    println("耗时：${System.currentTimeMillis() - start}ms")
}

执行结果：

凑成目标金额所需的最小零钱数：5 , 子问题总数是12956
耗时：4ms

心算一下，18块钱，拆分成(1,2,5)零钱，应该是需要3x5+2x1+1x1 , 所以零钱的张数是 3+1+1 = 5. 可以看到，仅仅是很小的金额的计算，这种穷举的暴力解法，居然要将近1万3千次运算。可想而知其中有多少是无用功。

一重改进

既然是无用功，那么使用map保存已经计算出的结果，再次求值时，不必重新计算，而是直接取值。

import java.lang.Integer.min

val change = arrayOf(1, 2, 5) // 零钱就是1,2,5

var calCount = 0

/**
 * 优化方案1:用一个容器把已经计算出来的结果保存起来,计算之前先看容器中有没有,有就直接取，没有就去计算，计算之后存入容器
 * @param targetAmount 要用零钱凑成的目标金额
 * 进行if return/continue 优化
 */
fun changeMoney2(map: HashMap<Long, Int>?, targetAmount: Long): Int {
    val mapThis = map ?: HashMap()// 如果是空，就创建

    var finalCount = Int.MAX_VALUE // 由于要计算出最小值，所以先初始化为最大值
    if (targetAmount == 0L) return 0
    if (targetAmount < 0) return -1
    for (c in change) {
        //要不要执行？先看容器里面有没有
        var cache = mapThis[targetAmount - c]
        if (cache == null) {// 如果找不到，就说明容器中没有
            cache = changeMoney2(mapThis, targetAmount - c)// 那就计算
            if (cache == -1) continue // -1异常情况就不要参与保存了
            mapThis[targetAmount - c] = cache // 保存
        }
        finalCount = min(finalCount, 1 + cache)// 最终结果记得+1,同時取最小值
        calCount++
    }

    println("计算过程：$finalCount  $mapThis")
    return finalCount
}

fun main() {
    val start = System.currentTimeMillis()
    val changeMoney = changeMoney2(null, 18)
    println("凑成目标金额所需的最小零钱数：$changeMoney , 子问题的总运算次数是：${calCount}")
    println("耗时：${System.currentTimeMillis() - start}ms")
}

执行结果：

计算过程：5  {0=0, 1=1, 2=1, 3=2, 4=2, 5=1, 6=2, 7=2, 8=3, 9=3, 10=2, 11=3, 12=3, 13=4, 14=4, 15=3, 16=4, 17=4}
凑成目标金额所需的最小零钱数：5 , 子问题的总运算次数是：49
耗时：5ms

子问题的运算次数，从之前的上万次，直接降低为18次。

但是运行耗时几乎没有变化。这是由于目标数值太少，仅仅是18，还不足以看出算法耗时的差别。换成158,1588试试看

零钱依然假定为k种

时间复杂度：

时间复杂度降低为O(2kn), 直接从之前的k的指数级别，降低为k的1次方。运算次数骤减。

空间复杂度：

即使子问题的个数是n，但是由于共享hashmap的原因，空间复杂度是 O(n)

二重改进

把从上而下的逆向递归，改成更容易理解的从下而上的遍历。先计算出f(1),f(2)...最后计算到最终值f(18).

import java.lang.Integer.min

val change = arrayOf(1, 2, 5) // 零钱就是1,2,5

var calCount = 0

fun changeMoney3(lastTarget: Int): Int {
    // 所以做法就是，从0开始往后推演，从树根往树顶推算
    val hashMap = HashMap<Int, Int>()
    var result = -1
    for (currentTarget in 1..lastTarget) {
        result = getMin(currentTarget, hashMap)
    }
    println("最终保存的map内容是：$hashMap ")
    return result
}

fun getMin(currentTarget: Int, map: HashMap<Int, Int>): Int {
    if (map.containsKey(currentTarget)) {
        println("找到已经存在的记录: map[${currentTarget}]=${map[currentTarget]!!}")
        return map[currentTarget]!!
    }
    var res = Int.MAX_VALUE
    loop@ for (c in change) {
        val currentRes = when {
            currentTarget - c == 0 -> {
                map[currentTarget] = 1
                1
            }
            currentTarget - c > 0 -> {
                val x = 1 + getMin(
                    currentTarget - c,
                    map
                )/* 1表示当前金额,getMin(currentTarget - c, map) 表示去掉当前金额之后，所需零钱数 */
                calCount++
                map[currentTarget] = x // 保存起来
                x
            }
            else -> {
                continue@loop
            }
        }
        res = min(res, currentRes)
    }

    return res
}

//测试代码
fun main() {
    val start = System.currentTimeMillis()
    val changeMoney3 = changeMoney3(18)
    println("凑成目标金额所需的最小零钱数：$changeMoney3 子问题运算次数为：${calCount}")
    println("耗时：${System.currentTimeMillis() - start}ms")
}

运行结果：

最终保存的map内容是：{1=1, 2=1, 3=2, 4=2, 5=1, 6=2, 7=2, 8=3, 9=3, 10=2, 11=3, 12=3, 13=4, 14=4, 15=3, 16=4, 17=4, 18=5} 
凑成目标金额所需的最小零钱数：5 子问题运算次数为：46
耗时：5ms

零钱数依然设定为K

时间复杂度：

时间复杂度降低为O(2kn)

空间复杂度：

即使子问题的个数是n，但是由于共享hashmap的原因，空间复杂度是 O(n)

复杂度和上面一种解法一样！但是思维上，比上一种更容易理解，更人性化。

三重改进

之前我是用map来保存前一步计算出的值，尝试一下能否不用map，而只是用循环内的临时变量来存。

但是发现不行，因为 这个问题不能类比 斐波拉契数列, 运算结果的依赖性比斐波拉契数列更加复杂。所以作罢。

结语

以凑零钱问题为例，展示 动态规划算法的实战应用价值。相信本文已经解析的很清楚了。就是这么一个套路。其他 最值问题也差不多按照这个套路，做出最优解也只是时间问题。

但是，现实中，我们不会只想知道零钱最少需要多少张，我还想知道零钱怎么组合最优,怎么解?并且 零钱可能无限多么？如果零钱数目有限，那上面的解法又该如何修改？ 篇幅太长不利于阅读，我把解答放到下一章。

尽请期待！

上一篇下一篇

猜你喜欢

热点阅读