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
}