0-1ナップサック アルゴリズム

何が書いてあるか。

0-1ナップサック問題¹のアルゴリズムのGo言語実装サンプル

package main
import (
    "fmt"
    "math"
    )
type Kingyo struct {
    weight int
    kati int
}
func main(){    
    var N,x int
    fmt.Scanf("%d %d", &N,&x)
    
    kingyo:=make([]Kingyo,N)
    for i:=0;i<N;i++ {
        var w,k int
        fmt.Scanf("%d %d", &w,&k)
        kingyo[i]=Kingyo{w,k}
    }
    
    //fmt.Println(kingyo)
    
    choice:=make([][]int, N+1)
    for i:=0;i<N+1;i++ {
        choice[i]=make([]int, x+1)
    }
    
    for i:=1;i<=N;i++ {
        for j:=0;j<=x;j++ {
            choice[i][j]=choice[i-1][j]
            if j>kingyo[i-1].weight {
                choice[i][j]=int( math.Max( float64(choice[i][j]), float64(choice[i-1][j-kingyo[i-1].weight]+kingyo[i-1].kati)) )
            }
        }
    }
    
    //dump(choice)
    fmt.Println(choice[N][x])
}

func dump(choice [][]int) {
    for i:=0;i<len(choice);i++ {
        fmt.Println(choice[i])
    }
}

1. 重量を越えないような物の組み合わせのうち、価値が最大になるようにな組み合わせを求める問題。 ↩