题目描述
blablabla
样例
package main
import "fmt"
const N int = 110
var n, m int
var v [N][N]int
var w [N][N]int
var s [N]int
var dp [N]int
func main(){
fmt.Scanf("%d %d", &n, &m)
for i := 0; i < n; i++{
fmt.Scan(&s[i])
for j := 0; j < s[i]; j++{
fmt.Scanf("%d %d", &v[i][j], &w[i][j])
}
}
for i := 0; i < n; i++{
for j := m; j >= 0; j--{
for k := 0; k < s[i]; k++{
if v[i][k] <= j{
dp[j] = max(dp[j], dp[j-v[i][k]] + w[i][k])
}
}
}
}
fmt.Println(dp[m])
}
func max(i, j int)int{
if i > j{
return i
}
return j
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla