假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。
输入示例:
const weight = 100;
输出示例:
getResult(weight) // 15 其中7g的14个,2g的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)
}
###
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)