貪心算法的思想

即對于目標T，對于達成它的每一局部都選擇最優(yōu)選項，直到滿足或最終近似滿足為止，最終結(jié)果或許不是全局最優(yōu)解，但應(yīng)該是近似最優(yōu)解，因為它足夠簡單。

每一步都采取局部最優(yōu)做法！
貪婪算法大多時候都是近似最優(yōu)算法！

貪心算法的三步走：

第一步：明確到底什么是最優(yōu)解？
第二步：明確什么是子問題的最優(yōu)解？
第三步：分別求出子問題的最優(yōu)解再堆疊出全局最優(yōu)解？

貪心算法的前提：

• 原問題復(fù)雜度過高；
• 求全局最優(yōu)解的數(shù)學(xué)模型難以建立；
• 求全局最優(yōu)解的計算量過大；
• 沒有太大必要一定要求出全局最優(yōu)解，“比較優(yōu)”就可以。
  以上情況幾乎99.99999999999%就要使用貪心算法的思想來解決問題！

分解子問題的方法：

1.按串行任務(wù)分：時間串行的任務(wù)，按子任務(wù)來分解，即每一步都是在前一步的基礎(chǔ)上再選擇當前的最優(yōu)解。
2.按規(guī)模遞減分：規(guī)模較大的復(fù)雜問題，可以借助遞歸思想，分解成一個規(guī)模小一點點的問題，循環(huán)解決，當最后一步的求解完成后就得到了所謂的“全局最優(yōu)解”。
3.按并行任務(wù)分：這種問題的任務(wù)不分先后，可能是并行的，可以分別求解后，再按一定的規(guī)則（比如某種配比公式）將其組合后得到最終解。

如何知道貪心算法結(jié)果逼近全局最優(yōu)解？

正因為有些問題很難求到全局最優(yōu)解，才有貪心算法，它需要考慮成本、速度、價值： 成本：耗費多少資源，花掉多少編程時間。 速度：計算量是否過大，計算速度能否滿足要求。 價值：得到了最優(yōu)解與次優(yōu)解是否真的有那么大的差別，還是說差別可以忽略。

例題

0-1背包問題 有一個背包，最多能承載150斤的重量，現(xiàn)在有7個物品， 重量分別為[35, 30, 60, 50, 40, 10, 25]， 它們的價值分別為[10, 40, 30, 50, 35, 40, 30]， 每個物品要么選擇要么放棄， 應(yīng)該如何選擇才能使得我們的背包背走最多價值的物品？

解法:

• 第一步：明確到底什么是最優(yōu)解？ —— 在重量限制內(nèi)，價值最大的就是最優(yōu)解；
• 第二步：明確什么是子問題的最優(yōu)解？這就是"局部最優(yōu)解"
  • 方案一：每一次都盡量選擇當前價值最高的物品
  • 方案二：每次盡量選擇重量最小的物品
  • 方案三：每次盡量選擇價值密度高的物品，即單位重量價值高的物品
• 第三步：分別求出子問題的最優(yōu)解再堆疊出全局最優(yōu)解？

解題步驟及Go語言描述：

方案一：按照制訂的規(guī)則（價值）進行計算，數(shù)組索引順序是：3 1 5 4 ；最終的總重量是：130 ；最終的總價值是：165。
方案二：按照制訂的規(guī)則（重量）進行計算，數(shù)組索引順序是：5 6 1 0 4 ；最終的總重量是：140；最終的總價值是：155。可以看到，重量優(yōu)先是沒有價值優(yōu)先的策略更好。
方案三：按照制訂的規(guī)則（單位密度）進行計算，數(shù)組索引順序是：5 1 6 3 4；最終的總重量是：150；最終的總價值是：170。可以看到，單位密度這個策略比之前的價值策略和重量策略都要好。

type good struct {
    // name   string
    weight int
    price  int
    status int // 0未選中，1已選中
}

var maxWeight = 150
var goods = []good{
    good{35, 10, 0},
    good{30, 40, 0},
    good{60, 30, 0},
    good{50, 50, 0},
    good{40, 35, 0},
    good{10, 40, 0},
    good{25, 30, 0},
}

// 解法一：每一次都盡量選擇當前價值最高的物品
// 按照制訂的規(guī)則（價值）進行計算，數(shù)組索引順序是：3 1 5 4 ；最終的總重量是：130 ；最終的總價值是：165。
func GreedyKnapsack1(goods []good, maxW int) (totalP, totalW int) {
    // 物品總數(shù)
    n := len(goods)
    // 選物品
    for totalW <= maxW {
        // 選出余下價格最大的物品
        maxPIndex := -1
        maxPrice := goods[0].price
        for i := 0; i < n; i++ {
            if goods[i].status == 0 && goods[i].price > maxPrice {
                maxPIndex = i
                maxPrice = goods[i].price
            }
        }
        // 如計算超出重量則退出
        if totalW+goods[maxPIndex].weight > maxW {
            break
        }
        // 累計
        goods[maxPIndex].status = 1
        totalW += goods[maxPIndex].weight
        totalP += goods[maxPIndex].price
        fmt.Println("select good:", goods[maxPIndex], ",index:", maxPIndex, ",total weight:", totalW)
    }
    fmt.Println("goods:", goods)

    return

}

// 解法二：每次盡量選擇重量最小的物品
// 按照制訂的規(guī)則（重量）進行計算，數(shù)組索引順序是：5 6 1 0 4 ；最終的總重量是：140；最終的總價值是：155?？梢钥吹?，重量優(yōu)先是沒有價值優(yōu)先的策略更好。
func GreedyKnapsack2(goods []good, maxW int) (totalP, totalW int) {
    // 物品總數(shù)
    n := len(goods)
    // 選物品
    for totalW <= maxW {
        minWIndex := -1
        minWeight := math.MaxInt64
        // 選出余下重量最小的
        for i := 0; i < n; i++ {
            if goods[i].status == 0 && goods[i].weight <= minWeight {
                minWIndex = i
                minWeight = goods[i].weight
            }
        }

        // 如計算超出重量則退出
        if totalW+goods[minWIndex].weight > maxW {
            break
        }

        // 累計
        goods[minWIndex].status = 1
        totalW += goods[minWIndex].weight
        totalP += goods[minWIndex].price
        fmt.Println("select good:", goods[minWIndex], ",index:", minWIndex, ",total weight:", totalW)
    }
    fmt.Println("goods:", goods)

    return
}

// 解法三：每次盡量選擇價值密度高的物品，即單位重量價值高的物品
// 按照制訂的規(guī)則（單位密度）進行計算，數(shù)組索引順序是：5 1 6 3 4；最終的總重量是：115；最終的總價值是：160。可以看到，單位密度這個策略比之前的價值策略和重量策略都要好。
func GreedyKnapsack3(goods []good, maxW int) (totalP, totalW int) {

    // 物品總數(shù)
    n := len(goods)
    // 選物品
    for totalW <= maxW {
        maxDIndex := -1
        maxDensity := 0.0
        // 選出余下價格密度最高的
        for i := 0; i < n; i++ {
            if goods[i].status == 0 && float64(goods[i].price) / float64(goods[i].weight) > maxDensity {
                maxDIndex = i
                maxDensity = float64(goods[i].price) / float64(goods[i].weight)
            }
        }
        // fmt.Println("maxDIndex:",maxDIndex)
        // fmt.Println("maxDensity:",maxDensity)

        // 如計算超出重量則退出
        if totalW+goods[maxDIndex].weight > maxW {
            break
        }

        // 累計
        goods[maxDIndex].status = 1
        totalW += goods[maxDIndex].weight
        totalP += goods[maxDIndex].price
        fmt.Println("select good:", goods[maxDIndex], ",index:", maxDIndex, ",total weight:", totalW)
    }
    fmt.Println("goods:", goods)

    return
}

很顯然大多數(shù)方案不是全局最優(yōu)解，但只要是近似最優(yōu)解。優(yōu)點就是計算簡單，對于那些計算精確解需要極大代價的算法來說，貪心算法求解出近似解是不錯的選擇。