1.朴素DP: 二维DP + 三重for
package main
import "fmt"
func cal(N, V int, v, w []int) int {
var (
max = func(i, j int) int { if i > j { return i }; return j }
dp = make([][]int, N + 1)
)
for i := range dp { dp[i] = make([]int, V + 1) }
for i := 1; i <= N; i++ {
for j := 0; j <= V; j++ {
for k := 0; k * v[i] <= j; k++ {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i])
}
}
}
return dp[N][V]
}
func main() {
var (
ans int
N, V int
tmpV, tmpW int
v, w = []int{0}, []int{0}
)
fmt.Scanln(&N, &V)
for i := 1; i <= N; i++ {
fmt.Scanln(&tmpV, &tmpW)
v = append(v, tmpV)
w = append(w, tmpW)
}
ans = cal(N, V, v, w)
fmt.Println(ans)
}
2.二维DP
package main
import "fmt"
func cal(N, V int, v, w []int) int {
var (
max = func(i, j int) int { if i > j { return i }; return j }
dp = make([][]int, N + 1)
)
for i := range dp { dp[i] = make([]int, V + 1) }
for i := 1; i <= N; i++ {
for j := 0; j <= V; j++ {
dp[i][j] = dp[i - 1][j]
if j >= v[i] { dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]) }
}
}
return dp[N][V]
}
func main() {
var (
ans int
N, V int
tmpV, tmpW int
v, w = []int{0}, []int{0}
)
fmt.Scanln(&N, &V)
for i := 1; i <= N; i++ {
fmt.Scanln(&tmpV, &tmpW)
v = append(v, tmpV)
w = append(w, tmpW)
}
ans = cal(N, V, v, w)
fmt.Println(ans)
}
3.终极优化: 一维DP
package main
import "fmt"
func cal(N, V int, v, w []int) int {
var (
max = func(i, j int) int { if i > j { return i }; return j }
dp = make([]int, V + 1)
)
for i := 1; i <= N; i++ {
for j := v[i]; j <= V; j++ {
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
}
}
return dp[V]
}
func main() {
var (
ans int
N, V int
tmpV, tmpW int
v, w = []int{0}, []int{0}
)
fmt.Scanln(&N, &V)
for i := 1; i <= N; i++ {
fmt.Scanln(&tmpV, &tmpW)
v = append(v, tmpV)
w = append(w, tmpW)
}
ans = cal(N, V, v, w)
fmt.Println(ans)
}
4.另一优化写法:二维DP + 滚动数组
package main
import "fmt"
func cal(N, V int, v, w []int) int {
var (
max = func(i, j int) int { if i > j { return i }; return j }
dp = make([][]int, 2)
)
for i := range dp { dp[i] = make([]int, V + 1) }
for i := 1; i <= N; i++ {
for j := 0; j <= V; j++ {
dp[i % 2][j] = dp[(i - 1) % 2][j]
if j >= v[i] { dp[i % 2][j] = max(dp[i % 2][j], dp[i % 2][j - v[i]] + w[i]) }
}
}
return dp[N % 2][V]
}
func main() {
var (
ans int
N, V int
tmpV, tmpW int
v, w = []int{0}, []int{0}
)
fmt.Scanln(&N, &V)
for i := 1; i <= N; i++ {
fmt.Scanln(&tmpV, &tmpW)
v = append(v, tmpV)
w = append(w, tmpW)
}
ans = cal(N, V, v, w)
fmt.Println(ans)
}