js编程题:砝码最小数量问题

hzrWeb
  • 1.2k

假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。

输入示例:
const weight = 100;

输出示例:
getResult(weight) // 15 其中7g的14个,2g的1个

回复
阅读 736
3 个回答

动态规划问题:

function getResult (weights, amount) {
    var memo = {};

    function dp (n) {

        if (memo[n]) return memo[n];

        //  base case
        if (n == 0)
            return 0
        if (n < 0)
            return -1
        // # 求最小值,所以初始化为正无穷
        var res = Infinity;
        for (let weight of weights.values()) {
            subproblem = dp(n - weight)
            // # 子问题无解,跳过
            if (subproblem == -1)
                continue
            res = Math.min(res, 1 + subproblem)
        }
        res = res === Infinity ? -1 : res;
        memo[n] = res = res === Infinity ? -1 : res;
        return memo[n];
    }

    return dp(amount)
}

2g 3g 7g
他们能表示的克数有:2g;3g;2g+2g;2g+3g;3g+3g;7g;...
也就是除了1g不能表示外,其余的均能表示。

weight = 7x + 3y + 2z

weight减去7x,剩下的肯定是小于7的数。然后再用2g;3g;2g+2g;2g+3g;3g+3g;处理。

但是这块要考虑 weight=7x + 1的问题,这样必须用 weight=7(x-1) + 8才能表示。

我帮你召集了一堆人帮你回答。 求个赞不过分吧?https://github.com/azl3979858...

思路

懒得给DP解法了, 这个方法懂了,我相信DP难不倒你。

2g、3g、7g 为候选砝码,我们将其抽象为candidates[2,3,7],令f(n) 为 总重为n,所需砝码的最小数量

对于每一个砝码,我们可以选择或者不选择。

为了更好写代码,我们定义f(n,i) 为 总重为n,选择到第i个砝码,所需砝码的最小数量

  • 选择一次 f(n - candidates[i], i + 1) + 1
  • 选择一次以上就是 f(n - candidates[i], i) + 1 (类似正则中的+匹配)
  • 不选择就是 f(n, i + 1)

那么

f(n, i) = min(f(n, i + 1) , f(n - candidates[i], i ) + 1),因此我们只需要求 f(weights, 0) 即可。

代码

candidates = [2,3,7]
def f(n, i):
    if i > 2 or n < 0: return float('inf')
    if n == 0: return 0
    return  min(f(n, i + 1), f(n - candidates[i], i ) + 1)
# 测试
f(100, 0)

相关题目

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏