AcWing 2. 01背包问题-golang
原题链接
简单
作者:
渲染
,
2024-04-04 11:11:20
,
所有人可见
,
阅读 1
// package main
// import(
// "fmt"
// "os"
// "bufio"
// )
// const N int = 1010
//
// var f[N][N]int
// var w[N]int
// var v[N]int
// var reader = bufio.NewReader(os.Stdin)
// var n ,m int
// func max(x , y int)int{
// if x > y{
// return x
// }
// return y
// }
// func main(){
// fmt.Fscan(reader,&n,&m)
// for i:=1;i<=n;i++{
// fmt.Fscan(reader,&w[i],&v[i])
// }
// for i:=1;i<=n;i++{
// for j:=1;j<=m;j++{
// f[i][j] = f[i-1][j]
// if j >= w[i]{
// f[i][j] = max(f[i][j],f[i-1][j-w[i]]+v[i])
// }
// }
// }
// fmt.Println(f[n][m])
// }
package main
import(
"fmt"
"os"
"bufio"
)
const N int = 1010
var f[N]int
var w[N]int
var v[N]int
var reader = bufio.NewReader(os.Stdin)
var n ,m int
func max(x , y int)int{
if x > y{
return x
}
return y
}
func main(){
fmt.Fscan(reader,&n,&m)
for i:=1;i<=n;i++{
fmt.Fscan(reader,&w[i],&v[i])
}
for i:=1;i<=n;i++{
for j:=m;j>=w[i];j--{
f[j] = max(f[j],f[j-w[i]]+v[i])
}
}
fmt.Println(f[m])
}