AcWing 2. 01背包问题
原题链接
简单
作者:
Sam_2
,
2021-01-07 01:20:16
,
所有人可见
,
阅读 478
package main
import "fmt"
//0-1背包问题
/*
1:二维动态规划
f[i][j] 前i个物品, 体积<=j的最大价值
求f[n][v]
//根据第i件物品是否选
f[i][j] = f[i-1][j] + f[i-1][j-v[i]] + w[i]
//初始化
f[0][0~]=0
*/
/*
fmt.Scanf("%d", &n)
for i := 1; i <= n; i ++ {
fmt.Scanf("%d", &nums[i])
}
*/
func main() {
N,V := 0, 0
fmt.Scanf("%d%d", &N, &V)
vi, wi := make([]int, N+1), make([]int, N+1)
for i := 1; i <= N; i++ {
fmt.Scanf("%d%d", &vi[i], &wi[i])
}
f := make([]int, V+1)
for i := 1; i <= N; i++ {
for j := V; j >= 1; j-- {
if j - vi[i] >= 0 {
if f[j] < f[j-vi[i]] + wi[i] {
f[j] = f[j-vi[i]] + wi[i]
}
}
}
}
fmt.Printf("%v\n", f[V])
}