题解 | 完全背包

package main
// import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param v int整型 
 * @param n int整型 
 * @param nums int整型二维数组 
 * @return int整型一维数组
*/
func knapsack( v int ,  n int ,  nums [][]int ) []int {
    // write code here
    dp := make([]int, v+1)
    for i:=0;i<n;i++ {
        for j:=v;j >= nums[i][0];j-- {
            tmp := j
            cnt := 1
            for tmp >= cnt * nums[i][0] {
                dp[j] = max(dp[j], dp[j-nums[i][0] * cnt] + nums[i][1] * cnt)
                cnt++
            }
        }
    }
    dp2 := make([]int, v+1)
    for i:=0;i<v+1;i++ {
        dp2[i] = -99999
    }
    dp2[0] = 0
    for i:=0;i<n;i++ {
        for j:=v;j >= nums[i][0];j-- {
            tmp := j
            cnt := 1
            for tmp >= cnt * nums[i][0] {
                dp2[j] = max(dp2[j], dp2[j-nums[i][0] * cnt]  + nums[i][1] * cnt)
                cnt++
            }
        }
    }
    // fmt.Println(dp2)
    if dp2[v] < 0 {
        dp2[v] = 0
    }
    res := []int{dp[v],dp2[v]}
    return res
}

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