0-1 knapsack

递归 注释记忆化搜索

10背包

测试用例 背包大小5

10背包

耗时

10背包

添加记忆化搜索

10背包 10背包

package main

import (
    "fmt"
    "time"
)

func findbv(remainpack int,putted map[int]bool,curv int,kv [][]int,memo map[int]int) int{
    max:=curv
    for k,v:=range kv {
        if _,ok:=memo[remainpack];ok {
            if memo[remainpack]>max {
                fmt.Println("hit")
                max=memo[remainpack]
            }
        } else
        if remainpack-v[0]>=0 && putted[k]!=true {
            putted[k]=true
            a:=findbv(remainpack-v[0],putted,curv+v[1],kv,memo)
            putted[k]=false
            if max<a {
                max=a
            }
        }
    }
    memo[remainpack]=max
    return max
}

func main() {
    kv:=[][]int{
        {1,6},{2,10},{3,12},{5,6},{7,8},{9,33},{11,560},{1,6},
        {5,6},{7,8},{9,33},{11,560},{1,6},
        {5,6},{7,8},{9,33},{11,560},{1,6},
        {5,6},{7,8},{9,33},{11,560},{1,6},
        {5,6},{7,8},{9,33},{11,560},{1,6},
        {5,6},{7,8},{9,33},{11,560},{1,6},
        {5,6},{7,8},{9,33},{11,560},{1,6},
    }
    //kv=[][]int{
    //  {1,6},{2,10},{3,12},{5,23},
    //}
    start := time.Now()
    r:=findbv(13,make(map[int]bool),0,kv,make(map[int]int))
    //some func or operation
    cost := time.Since(start)
    fmt.Printf("cost=[%s]",cost)
    fmt.Println(r)
}

example :[w,v] [1,6] [2,10] [3,12]    pack: 5


greedy algorithm 近似最优

put bigger v/w into pack first until overflow


recusive + memorization   


findBiggestV(remainPack , putted,currV)


iterate all remainkvpair
    if memo[remainpack]
        return memo[remainpack]
    if remainpack-k>=0 && !putted
        putted[k]=true
        tmpc = currV+v
        currV = max(findBiggest(remainPack-k,tmpc) ,currV)

memo[remainpack]=currv
return currV


dynamic programming