Go语言解法

二维带K循环的解法

状态转移方程：

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

代码（TLE了）：

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 [MAX]int
    fmt.Scanln(&N, &V)
    for i:=1; i<=N; i++ {
      fmt.Scanln(&v[i], &w[i])
    }
    var dp [MAX][MAX]int
    for i := 1; i <= N; i++ {
        for j := 1; j <= V ; j++ {
            dp[i][j] = dp[i-1][j]
            for k:=1; k*v[i] <= j; k++ {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*v[i]]+k*w[i])     
            }
        }
    }
    fmt.Println(dp[N][V])
}

二维解法：

状态转移方程

dp[i][j] = max(dp[i][j-w[i]] + v[i], dp[i-1][j])

代码

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 [MAX]int
    fmt.Scanln(&N, &V)
    for i:=1; i<=N; i++ {
      fmt.Scanln(&v[i], &w[i])
    }
    var dp [MAX][MAX]int
    for i := 1; i <= N; i++ {
        for j := 0; j <= V ; j++ {
            if  j >= v[i] {
                dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]]+w[i])     
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    fmt.Println(dp[N][V])
}

一维解法

状态转移方程

dp[k] = max(value[i]+dp[k-weight[i]], dp[k])

代码

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 [MAX]int
    fmt.Scanln(&N, &V)
    for i:=1; i<=N; i++ {
      fmt.Scanln(&v[i], &w[i])
    }
    var dp [MAX]int
    for i := 1; i <= N; i++ {
        for j := v[i]; j <= V ; j++ {
            if  j >= v[i] {
                dp[j] = max(dp[j], dp[j-v[i]]+w[i])     
            }
        }
    }
    fmt.Println(dp[V])
}