leetcode638_go_大礼包

题目

在LeetCode商店中，有许多在售的物品。

然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，

其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

示例 1:输入: [2,5], [[3,0,5],[1,2,10]], [3,2] 输出: 14

解释: 有A和B两种物品，价格分别为¥2和¥5。

大礼包1，你可以以¥5的价格购买3A和0B。

大礼包2，你可以以¥10的价格购买1A和2B。

你需要购买3个A和2个B，所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

示例 2:输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] 输出: 11

解释: A，B，C的价格分别为¥2，¥3，¥4.

你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。

你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。

你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。

说明:最多6种物品， 100种大礼包。

每种物品，你最多只需要购买6个。

你不可以购买超出待购清单的物品，即使更便宜。

提示：n == price.length

n == needs.length

1 <= n <= 6

0 <= price[i] <= 10

0 <= needs[i] <= 10

1 <= special.length <= 100

special[i].length == n + 1

0 <= special[i][j] <= 50

解题思路分析

1、深度优先搜索；时间复杂度O(n^n)，空间复杂度O(n)

func shoppingOffers(price []int, special [][]int, needs []int) int {
   return dfs(price, special, needs)
}

func dfs(price []int, special [][]int, needs []int) int {
   res := 0
   for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
      res = res + needs[i]*price[i]
   }
   for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
      temp := make([]int, len(needs))
      copy(temp, needs) // 复制，避免还原
      j := 0
      for j = 0; j < len(temp); j++ {
         if temp[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
            break
         }
         temp[j] = temp[j] - special[i][j]
      }
      if j == len(temp) { // 可以取该礼包，继续递归
         res = min(res, dfs(price, special, temp)+special[i][j]) // 递归，取最小
      }
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

2、回溯；时间复杂度O(n^n)，空间复杂度O(n)

func shoppingOffers(price []int, special [][]int, needs []int) int {
   return dfs(price, special, needs)
}

func dfs(price []int, special [][]int, needs []int) int {
   res := 0
   for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
      res = res + needs[i]*price[i]
   }
   for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
      j := 0
      for j = 0; j < len(needs); j++ {
         if needs[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
            break
         }
      }
      if j == len(needs) { // 可以取该礼包，继续递归
         for k := 0; k < len(needs); k++ {
            needs[k] = needs[k] - special[i][k]
         }
         res = min(res, dfs(price, special, needs)+special[i][j]) // 递归，取最小
         for k := 0; k < len(needs); k++ {
            needs[k] = needs[k] + special[i][k]
         }
      }
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

3、回溯+缓存；时间复杂度O(n^n)，空间复杂度O(n)

var m map[string]int

func shoppingOffers(price []int, special [][]int, needs []int) int {
   m = make(map[string]int)
   return dfs(price, special, needs)
}

func dfs(price []int, special [][]int, needs []int) int {
   if v, ok := m[getString(needs)]; ok {
      return v
   }
   res := 0
   for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
      res = res + needs[i]*price[i]
   }
   for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
      j := 0
      for j = 0; j < len(needs); j++ {
         if needs[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
            break
         }
      }
      if j == len(needs) { // 可以取该礼包，继续递归
         for k := 0; k < len(needs); k++ {
            needs[k] = needs[k] - special[i][k]
         }
         res = min(res, dfs(price, special, needs)+special[i][j]) // 递归，取最小
         for k := 0; k < len(needs); k++ {
            needs[k] = needs[k] + special[i][k]
         }
      }
   }
   m[getString(needs)] = res
   return res
}

func getString(arr []int) string {
   res := ""
   for i := 0; i < len(arr); i++ {
      res = res + fmt.Sprintf("%d,", arr[i])
   }
   return strings.TrimRight(res, ",")
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

4、递归；时间复杂度O(n^n)，空间复杂度O(n)

func shoppingOffers(price []int, special [][]int, needs []int) int {
   res := 0
   for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
      res = res + needs[i]*price[i]
   }
   for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
      temp := make([]int, len(needs))
      copy(temp, needs) // 复制，避免还原
      j := 0
      for j = 0; j < len(temp); j++ {
         if temp[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
            break
         }
         temp[j] = temp[j] - special[i][j]
      }
      if j == len(temp) { // 可以取该礼包，继续递归
         res = min(res, shoppingOffers(price, special, temp)+special[i][j]) // 递归，取最小
      }
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}