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

Question

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

输入示例：
const weight = 100;

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

Answer 1

动态规划问题：

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)
}

Answer 2

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才能表示。

Answer 3

我帮你召集了一堆人帮你回答。 求个赞不过分吧？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)

相关题目

• 322.coin-change
• 518.coin-change-2
• 416.partition-equal-subset-sum