[ 0/1 ] Knapsack Problem

Knapsack problem 將一群物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包沒有容量限制，無論物品是什麼形狀大小，都能塞進背包； 但是背包有重量限制，如果物品太重，就會撐破背包

「 0/1 」 每種物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。

題目 :

以上, 如果於背包總重量 8 時, 裝進的水果組合為最高價值是多少 ?

思路 : (可參考 https://liuhongyi1.gitbooks.io/algorithm/content/DP_TotalInclude.html)

//// k -> 目前背包剩餘重量
//// 條件 :
// 發生如果 arr[n].weight > k (表示沒選中, 此輪價值為 0)
if k > 0 && arr[n].weight > k :
    sub(arr[0~n], k) = sub(arr[0 ~(n-1)], k) + 0
// 正常情況 (比較 選目前的水果 和 下一個水果誰的價值大)
if k > 0:
    sub(arr[0~n], k) = or(sub(arr[0 ~ (n-1)], k - arr[n].weight) + arr[n].value, sub(arr[0 ~ (n-1)], k) + 0)

//// 終止 :
// 正常情況 (背包已經沒有重量)
if k == 0:
    return 0
// 剛好計算到只剩一筆 (看目前水果的重量是否等於 k, 如果是 return arr[0].value 回去否則 return 0)
if len(arr) == 1 && arr[0].weight == k :
    return arr[0].value
else :
    return 0

code (golang) common

package main

import (
    "fmt"
)

type Item struct{
    Item string
    Weight int
    Value int
}

var gWorkArray []*Item

func prepare(){
    gWorkArray = make([]*Item, 5)
    gWorkArray[0] = &Item{Item: "Apple", Weight:4, Value:4500}
    gWorkArray[1] = &Item{Item: "Orange", Weight:5, Value:5700}
    gWorkArray[2] = &Item{Item: "Banana", Weight:2, Value:2250}
    gWorkArray[3] = &Item{Item: "Lemon", Weight:1, Value:1100}
    gWorkArray[4] = &Item{Item: "Grape", Weight:6, Value:6700}
}

func max(a1 *int, a2 *int) int{
    if *a1 >= *a2{
        return *a1
    }
    return *a2
}

code (golang) 遞迴 (result : 9050)

func recursive(array []*Item, sum int) int{
    totalCount := len(array)
    if sum == 0{
        return 0
    }

    if totalCount == 1{
        if array[0].Weight == sum{
            return array[0].Value
        }else{
            return 0
        }
    }

    lastIndex := totalCount - 1

    if array[lastIndex].Weight > sum{
        return recursive(array[0: totalCount - 1], sum) + 0
    }

    selectionValue := recursive(array[0: totalCount - 1], sum - array[lastIndex].Weight) + array[lastIndex].Value
    noSelectionValue := recursive(array[0: totalCount - 1], sum) + 0
    return max(&selectionValue, &noSelectionValue)
}

func main(){
    prepare()
    fmt.Println("Recursive total weight 8 max value ->", recursive(gWorkArray, 8))
}

code (golang) 動態規劃 (result : 9050)

func getDpArray(totalSum int)[][]int{
    // dpArray[item][w]
    dpArray := make([][]int, len(gWorkArray))
    for i:= 0; i < len(gWorkArray); i++{
        dpArray[i] = make([]int, totalSum + 1)
        for j:= 0; j < (totalSum + 1); j++{
            dpArray[i][j] = 0
        }
    }
    return dpArray
}

func dp(sum int) int{
    dpArray := getDpArray(sum)
    // if w = 0
    for i:= 0; i < len(gWorkArray); i++{
        dpArray[i][0] = 0
    }
    // len(0)
    if gWorkArray[0].Weight <= sum{
        dpArray[0][gWorkArray[0].Weight] = gWorkArray[0].Value
    }
    // -- start arr[1][1] .. arr[1][2] ... end
    for itemIndex := 1; itemIndex < len(gWorkArray); itemIndex++{
        for sumIndex := 1; sumIndex < (sum + 1); sumIndex++{
            if gWorkArray[itemIndex].Weight > sumIndex{
                dpArray[itemIndex][sumIndex] = dpArray[itemIndex - 1][sumIndex] + 0
            }else{
                selection := dpArray[itemIndex - 1][sumIndex - gWorkArray[itemIndex].Weight] + gWorkArray[itemIndex].Value
                noSelection := dpArray[itemIndex - 1][sumIndex] + 0
                dpArray[itemIndex][sumIndex] = max(&selection, &noSelection)
            }
        }
    }
    return dpArray[len(gWorkArray)-1][sum]
}

func main(){
    prepare()
    fmt.Println("Dp total weight 8 max value ->", dp(8))
}