动态规划之“背包问题”

发表于 | 分类于 | 阅读次数:
字数统计: 2,244 | 阅读时长 ≈ 11

做个找硬币的问题，然后自己啃了一下相关的动态规划的资料，随笔如下

题目要求如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

我写的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange1 = function(coins, amount) {
  let result = 0
  let  temp = []
  //优化的结果，由于原始的递归式中，会有大量重复计算，所以把重复计算的东西存储下来。用空间换时间
  for(let i = 0; i < coins.length; i++) temp.push([])
  function dp(index, coin, amou){
    if(amou == 0) return 0
    if(index >= coin.length) return Infinity
    if(amou < 0) return Infinity 

    if(temp[index][amou] !== undefined )  return  temp[index][amou]
    //每次都有两种选择方法
    //选择取当前的，取了之后（由于不是01问题所以还可以取，所以下标不变，目标减少）
    let a = dp(index, coin, amou - coin[index]) + 1
    //不取当前的，直接取后面的，则目标不变，下标改变
    let b = dp(index + 1, coin, amou)
    //我们看这两种哪一种取得的硬币书目少就取那种
    let res = Math.min(a, b)
    //index 为使用哪种硬币，amoun 是目标
    temp[index][amou] = res
    return res
  }
  result = dp(0, coins, amount) 
  //找不到等结果为 Indinity
  if(result ==  Infinity) return -1
  return result
};
/* 
使用上面的递归式，一开始比较纠结的是那个二维数组的结构，为什么是 temp[index][amou] ,而不是 temp[amou][index] 或者其他，我们想一下人来试验拿的时候如何去拿（枚举所有结果），先从小的开始拿，比如我只拿 coins[0] 即我只用 1，那么我要11个1，然后继续我用coins[0] 和 coin[1] 两种硬币，那么我会先看 2 需要几个，然后不够的用 1 来补充，我们考虑到硬币是整数的，然后不同的硬币的组合也是整数的，所以我们是不是可以这样子想，我目标是11，我用 5 个 2 得到了 10 ，然后需要 1 个 1 ，人可以很直观的看到，机器不可以，那么我们是不是可以给一个检索信息，就是 使用 1 这种硬币拼出 1 这个目标需要多少枚硬币，我们是不是只需要看temp[index][amou]的结果就好了。
然后得到了优化后的递归式，我们来试着写他的地推式
*/
var coinChange2 = function(coins, amount) {
  let temp = []
  if(amount === 0) return 0
  if(amount < 0) return -1
  if(coins.length == 0 && amount > 0) return -1
  //我们需要知道是的递推式是递归式的自下向上的写法，所以我们此时需要明确的是底到底是谁？
  //我们通过看上面的其实可以看到递归式的最后是index = 2，但是我们需要知道index = 2的状态是
  //由边界条件生成的，所有我们需要提前手动生成一个可以推出 index = 2 的东西 
  for(let i = 0 ; i <= coins.length; ++i) temp.push([])
  temp.forEach(item => {
    for(let i = 0 ; i <= amount; ++i) item.push(Infinity)
  })
  //由于 index = 3 即没有这种硬币，所以只有为 0 不找钱的时候有结果 0
  temp[coins.length][0] = 0
  
  for(let k = coins.length - 1; k >= 0 ; k--){
    for(let j = 0; j <= amount; j++){
      //这个是我不用这种硬币，使用下一种硬币
      temp[k][j] = temp[k + 1][j]
      //这个是我们此时用的硬币大于目标，只用使用下一种，所以不进入循环
      //如果小于那么结果就是 取了一枚硬币 + amoun 减去此时硬币的数值后的对应值需要的硬币数
      //我们之所以用循环是因为，我们使用此时的硬币后，我还可以选择这个硬币，所以我还需要重复这个步骤
      //即我还可以再取这个硬币
      for(let i = 1; i <= amount/coins[k]  ; i++) {
        let pre = temp[k][j - coins[k] * i]
        if(pre < Infinity) temp[k][j] = Math.min(temp[k][j], pre + i)
      }
    }
  }
  if(temp[0][amount] < Infinity) return temp[0][amount]
  return -1
}
/*
上面的时间复杂度很高，所以需要简化一下
*/
var coinChange3 = function(coins, amount) {
  let temp = []
  if(amount === 0) return 0
  if(amount < 0) return -1
  if(coins.length == 0 && amount > 0) return -1
  
  for(let i = 0 ; i <= coins.length; ++i) temp.push([])
  temp.forEach(item => {
    for(let i = 0 ; i <= amount; ++i) item.push(Infinity)
  })
  temp[coins.length][0] = 0
  for(let k = coins.length - 1; k >= 0 ; k--){
    for(let j = 0; j <= amount; j++){
      if( j - coins[k] > 0){
      //我们去掉了这个循环，是因为我们想一下，取了当前的硬币，然后最小的硬币数目，就是使用当前硬币数的 
      //amoun - 硬币面额 后的目标 需要最小硬币数  + 1 （我们此时取的硬币）
      let a = temp[k + 1][j]
      let b = temp[k][j - coins[k]] 
      temp[k][j] = Math.min(a, b + 1)
      } else {
        temp[k][j] = temp[k + 1][j]
      }
    }
  }
  if(temp[0][amount] < Infinity) return temp[0][amount]
  return -1
}
/*
时间复杂度降低了，我们试着降低一下空间复杂度
*/

var coinChange4 = function(coins, amount) {
  let temp = []
  if(amount === 0) return 0
  if(amount < 0) return -1
  if(coins.length == 0 && amount > 0) return -1
  
  for(let i = 0 ; i <= amount; ++i) temp.push(Infinity)
  temp[0] = 0

  for(let k = coins.length - 1; k >= 0 ; k--){
    for(let j = 0; j <= amount; j++){
      if(j - coins[k] > 0){
        let a = temp[j]
        let b = temp[j - coins[k]]
        temp[j] = Math.min(a, b + 1)
      } else {
      temp[j] = temp[j]
      }
    }
  }
  if(temp[amount] < Infinity) return temp[amount]
  return -1
}
/*
这个文字不好描述，一般动态规划都可以使用滚动数组来存放，然后我们发现这个东西用到的都是数组的一半空间
所以使用一个一维数组，需要自己画一下图就可以理解了
*/

console.log(coinChange([1,2,5],11))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*我们如果硬币不能重复呢？，我们如何做*/
var coinChangeTwo1 = function(coins, amount) {
 let result = 0

  function dp(index, coin, amou){
   if(amou === 0) return 0 
   if(amou < 0) return Infinity
   if(index > coin.length) return Infinity
    //不管用不用，我们都要给下标加 1  
    let a = dp(index + 1, coin, amou - coin[index]) + 1
    let b = dp(index + 1, coin, amou)
    return Math.min(a, b)
  }

  result =  dp(0, coins, amount)
  if(result !== Infinity) return result
  return -1
 }
/*我们试着自底向上写出递推式*/
var coinChangeTwo2 = function(coins, amount) {
  let result = 0
  let temp = []
  if(amount === 0) return 0
  if(amount < 0) return -1
  if(coins.length == 0 && amount > 0) return -1

  for(let i = 0 ; i <= coins.length; ++i) temp.push([])
  temp.forEach(item => {
    for(let i = 0 ; i <= amount; ++i) item.push(Infinity)
  })

  temp[coins.length][0] = 0
  for(let i = coins.length - 1; i >= 0; i--){
    for(let j = 0; j <= amount; ++j){
      //我们需要考虑如果我取了这个硬币，这个硬币不应该大于目标数额
         if(j - coins[i]  >= 0) {
          let a = temp[i + 1][j]
          let b = temp[i + 1][j - coins[i]] + 1
          temp[i][j] = Math.min(a, b)
         } else {
      //如果硬币大于目标数额，无法取当前的硬币     
          temp[i][j] = temp[i + 1][j]
         }
    }
  }
  result = temp[0][amount]
  if(result !== Infinity) return result
  return -1
 }
/*
我们是可以利用滚动数组再优化的，然后如果我们需要知道我使用了那些硬币呢？我该如何操作
我想到的是保留这些数据然后反向查询
*/
var coinChangeTwo3 = function(coins, amount) {
  let result = 0
  let temp = []
  if(amount === 0) return 0
  if(amount < 0) return -1
  if(coins.length == 0 && amount > 0) return -1

  for(let i = 0 ; i <= coins.length; ++i) temp.push([])
  temp.forEach(item => {
    for(let i = 0 ; i <= amount; ++i) item.push(Infinity)
  })

  let fonit = []
  temp[coins.length][0] = 0
  for(let i = coins.length - 1; i >= 0; i--){
    for(let j = 0; j <= amount; ++j){
      temp[i][j] = temp[i + 1][j]
         if(j - coins[i]  >= 0) {
          let a = temp[i + 1][j]
          let b = temp[i + 1][j - coins[i]] + 1
          temp[i][j] = Math.min(a, b)
         }
    }
  }
  let w = temp[0][amount]
  let s = 0
  let am = amount
  //我们看我们用了几个硬币，且我们可以拼出目标结果
  while(w > 0 && w !== Infinity) {
    //如果一个数据的下一行不是无穷大，那么说明我没有取这一行的硬币
    if(temp[s + 1][am] !== Infinity) s = s + 1
    //如果是无穷大，我必须要取这一行的硬币，
    if(temp[s + 1][am] == Infinity) {
      fonit.push(s)
      am = am - coins[s] 
      s = s + 1
      w--
    }
  }

  console.log(fonit)
  
  result = temp[0][amount]
  if(result !== Infinity) return result
  return -1
 }

我没有写没有可以重复取硬币的记录，不过大同小异

感觉不错的话给博主赞助一下呗