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
| // @Title: 大礼包 (Shopping Offers)
// @Author: 15816537946@163.com
// @Date: 2021-10-25 00:42:06
// @Runtime: 0 ms
// @Memory: 2.6 MB
func shoppingOffers(price []int, special [][]int, needs []int) int {
cost := 0
path := make([]int, len(price))
//先计算购买单品的价格,如果这个部分用dfs的话,太耗时
for k, v := range needs {
cost += v * price[k]
}
dfs(price, special, needs, path, 0, &cost, 0)
return cost
}
//path:当前购物总数;cur:当前消费金额; cost:最小消费金额;pos:当前礼包位置
func dfs(price []int, special [][]int, needs []int, path []int, cur int, cost *int, pos int) {
if equal(needs, path) {
if cur < *cost {
*cost = cur
}
return
}
//choose 大礼包
for k, v:= range special {
if cur+v[len(v)-1] >= *cost || k < pos { //不允许选择前面的礼包,避免出现礼包1 2, 2 1重复计算的情况
continue
}
flag := true
for k1, v1 := range v {
if k1 < len(price) {
if path[k1] + v1 > needs[k1] {
flag = false
break //如果礼包里的商品数量大于待购清单,放弃该礼包
}
}
}
if flag {
for i:=0; i<len(price); i++ {
path[i] = path[i] + v[i]
}
dfs(price, special, needs, path, cur+v[len(v)-1], cost, k)
//cancle choose
for i:=0; i<len(price); i++ {
path[i] = path[i] - v[i]
}
}
}
//choose 单品
for k, v := range price {
cur += (needs[k] - path[k]) * v
}
if cur < *cost {
*cost = cur
}
}
func equal(a []int, b []int) bool {
if len(a) != len(b) {
return false
}
for k, v := range a {
if v != b[k] {
return false
}
}
return true
}
|