Go语言解法

二维带K循环解法

状态转移方程

dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i], dp[i-1][j]) (0< k && k * w[i] <= j && k <=num[i])

代码

package main
import "fmt"

const MAX int = 1010

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

func main() {
    var N, V int
    var v, w, num [MAX]int
    fmt.Scanln(&N, &V)
    for i:=1; i<=N; i++ {
      fmt.Scanln(&v[i], &w[i], &num[i])
    }
    var dp [MAX][MAX]int
    for i := 1; i <= N; i++ {
        for j := 0; j <= V; j++ {
            dp[i][j] = dp[i-1][j]  // 初始状态需要能够
            for k:=0; k*v[i] <= j && k <= num[i]; k++ {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]]+k*w[i])    
            }
        }
    }
    fmt.Println(dp[N][V])
}

一维带K循环解法

状态转移方程

dp[j] = max(dp[j-k*w[i]] + k*v[i], dp[j]) (0 < k && k * w[i] <= j && k <= num[i])

代码

package main
import "fmt"

const MAX int = 1010

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

func main() {
    var N, V int
    var v, w, num [MAX]int
    fmt.Scanln(&N, &V)
    for i:=1; i<=N; i++ {
      fmt.Scanln(&v[i], &w[i], &num[i])
    }
    var dp [MAX]int
    for i := 1; i <= N; i++ {
        for j := V; j >= v[i]; j-- {
            for k:=0; k*v[i] <= j && k <= num[i]; k++ {
                dp[j] = max(dp[j], dp[j-k*v[i]]+k*w[i])    
            }
        }
    }
    fmt.Println(dp[V])
}