[数据结构与算法]leetcode:大礼包（错误思路）

错误思路：
1.找出合理的礼包
2.按礼包节省的钱从多到少排序
3.买完礼包的剩下原价买

代码：

func shoppingOffers(price []int, special [][]int, needs []int) int {
    //银行家算法
    total := 0
    n := len(price)
    special_record := []int{}
    special_valid := [][]int{}
    
    //先求出每个大礼包节省的钱
    for i := 0; i < len(special); i++ {
        special_i_total := special[i][n]
        real_i_total := 0
        for j := 0; j < n; j++ {
            real_i_total += special[i][j] * price[j]
        }
        //记录有效的礼包的位置并记录节省的钱
        if real_i_total - special_i_total > 0 {
            special_record = append(special_record, i)
            special[i] = append(special[i], real_i_total - special_i_total)
        }
    }
    //抽取出有效的礼包放入special_valid
    for i := 0; i < len(special_record); i++ {
        special_valid = append(special_valid, special[special_record[i]])
    }
    //使用Slice接口直接用匿名函数对结构体/数组排序
    //按节约的钱大小排序
    m := len(special_valid)
    sort.Slice(special_valid, func (i, j int) bool {
        return special_valid[i][n+1] > special_valid[j][n+1]
    })
    
    //遍历完能用的大礼包
    for i := 0; i < m; i++ {
        if check(needs, special_valid[i]) {
            total += special_valid[i][n]
            for j := 0; j < n; j++ {
                needs[j] -= special_valid[i][j]
            }
            i--
        }
    }

    //剩下的单独结算
    for i := 0; i < n; i++ {
        total += needs[i] * price[i]
    }

    return total
}

func check(needs, special_valid []int) bool {
    n := len(needs)
    for i := 0; i < n; i++ {
        if needs[i] < special_valid[i] {
            return false
        }
    }
    return true
}

结果：

almost

反思：
用dfs求出礼包组合的最低价才行