Leetcode: 【每日一题】- 2020-05-27 - 砝码的最小数量

[azl397985856]

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

输入示例：
const weight = 100;

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

[qiyeal]

function getResult($weight)
{
        $arr = [7, 3, 2];
        $num = 0;
        foreach($arr as $item){
            if($weight <= 0){
                break;
            }
            $temp= intval($weight/$item);
            $weight = $weight - $item*$temp;

            $num += $temp;
        }
        return $num;
}

[azl397985856]

思路

懒得给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

[unclegem]

那就我来干脏活吧🍋

    public int getResult(int weight) {

        if (weight < 2)
            return -1;

        int[] arr = {2, 3, 7};

        int[] dp = new int[weight + 1];

        Arrays.fill(dp, weight + 1);
        dp[0] = 0;

        for (int i = 1; i <= weight; i++)
            for (int w : arr)
                if (i >= w)
                    dp[i] = Math.min(dp[i], dp[i - w] + 1);

        return dp[weight] == weight + 1 ? -1 : dp[weight];
    }

[wangxu-scu]

Python版DP：

def getWeight(candidates, n):
    f = [float('inf') for _ in range(n+1)]
    f[0] = 0
    for i in range(1, n+1):
    for c in candidates:
        if (i-c) >= 0:
            f[i] = min(f[i], f[i-c] + 1)
    return f[n]

if __name__ == "__main__":
    candidates = [2,3,7]
    n = 100
    print(getWeight(candidates, n))

[GrimaceL]

把砝码放在数组里，然后循环数组计算

def min_num(weight):
    minsum =0
    if(weight == 0):
        return minsum
    arr =[7,3,2]
    for i in arr:
        if(weight ==0):
            break
        sum = weight//i
        if(sum < -1):
            sum = sum +1
        weight = weight - sum*i
        minsum += sum
    return minsum 

[suukii]

补充一个 dp 的 JavaScript 版

思路

将图中的计算顺序倒转就行，也就是我们先计算 F(1)，然后 F(2) ... `F(6)。

代码

const foo = (weights, weight) => {
  const dp = Array(weight + 1).fill(weight + 1)
  dp[0] = 0

  for (let i = 1; i <= weight; i++) {
    for (let j = 0; j < weights.length; j++) {
      if (weights[j] <= i) {
        dp[i] = Math.min(dp[i - weights[j]] + 1 , dp[i])
      }
    }
  }
  return dp[weight] == weight + 1 ? -1 : dp[weight]
}
foo([2,3,7], 100)

[huangruitian]

// dp 无非就是枚举题目给的条件，我暂且叫它【状态】，然后通过【选择】计算得出结果；
// 由于题目给出的条件有两个，所以锁定两个【状态】是 砝码数 和 重量 两个变量；
// 对于每个砝码，我们可以有两个【选择】，一个是取当前砝码，另一个是不取；
// 答案肯定是枚举这两个【状态】，从中做一些最优的【选择】来得到答案
// 所以，我们可以肯定的得出算法框架；这里设 m 是砝码数，n是重量

for(let i = 0; i < m; i++){
  for(let j = 0; j < n; j++){
     if(当前砝码 > j重量){
      res = 不选择当前砝码
     }else{
      res = min(选择当前的砝码，不选择当前的砝码)
     } 
  }
}

// 前面我们的思路没有错，那么我们可以这样来【定义状态】
// 定义状态：dp[i][j] 表示前i个物品，j重量能装最少砝码数
// 由于是求最少的砝码数，我们初始化 dp[i][j] = Infinity，先代表无解
// 初始条件：就是当 dp[0...m][0] = 0，因为没有重量；肯定都能装嘛嘛；
// 边界条件：因为我们要使用没有重量的情况，而答案又求重量n，也就是0-n，所以边界就是 n+1

// 状态转移方程：你可以试着画出dp table；根据我们找出砝码的【选择】，就是取不取当前的砝码；
![微信图片_20200527225936](https://user-images.githubusercontent.com/30000503/83037176-10fbb700-a06e-11ea-865a-db391db1baac.png)

// 仔细观察，当问题的规模逐渐变大时候，数据之间有什么关系？我们很容易会发现；
// 最终的答案其实就是 res = min(取当前的砝码，不取当前的砝码)；
// 同时还要注意一个细节，当前的砝码重量大于当前重量；肯定不可以取；
// 结合我们的【定义状态】，所以最终的状态转移方程为：
// 不能取当前砝码：dp[i][j] = dp[i - 1][j]，candidates[i - 1] > j
// 能取当前砝码：dp[i][j] = Math.min(dp[i][j - candidates[i - 1]] + 1, dp[i - 1][j])

function getResult(weight = 100, candidates = [2, 3, 7]) {
  let n = weight;
  let m = candidates.length
  let dp = Array.from(new Array(m + 1), () => new Array(n + 1).fill(Infinity))
  for (let i = 0; i < m + 1; i++) {
    dp[i][0] = 0;
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if(candidates[i - 1] > j){
        dp[i][j] = dp[i - 1][j]
      }else{
        dp[i][j] = Math.min(dp[i][j - candidates[i - 1]] + 1, dp[i - 1][j])
      }
    }
  }
  return dp[m][n]
}
// 其实这题还可以压缩dp状态，留给你们思考了。
// 刷过dp的小伙伴，很容易就会发现这就是背包类型dp，属于完全背包问题；
// 如果是砝码只能选一次，就是最经典的01背包问题；
// 刷dp题不要过于关注细节，一定要先抽出，确定算法框架，自顶向下书学代码；

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.