分组背包问题-golang

分组背包问题-golang

package main

import "fmt"

var n, v int  //组数，容量
var num []int
var vi, wi, si [][]int  //每组第i个物品的体积和价值
var value []int

func main(){
    fmt.Scanf("%d%d", &n, &v)

    value = make([]int, v+1)
    vi, wi = make([][]int, n+1), make([][]int, n+1)
    num = make([]int, n+1)

    for i := 1; i <= n; i++{
         fmt.Scanf("%d", &num[i])  //当前物品组数量
         vi[i] = make([]int, num[i]+1)
         wi[i] = make([]int, num[i]+1)
         for j := 1; j <= num[i]; j++{
             fmt.Scanf("%d%d", &vi[i][j], &wi[i][j])
         }
    }


    for i := 1; i <= n; i++{
        for j := v; j > 0; j--{
             for k := 0; k <= num[i]; k++{
                 if j >= vi[i][k]{
                      value[j] = max(value[j], value[j-vi[i][k]] + wi[i][k])
                 }

             }
        }
    }
    fmt.Println(value[v])
}

func max(a, b int)int{
    if a > b{
        return a
    }
    return b
}