前情提要
这题是多重背包问题 I的基础上,强化了数据(难度++++)而来的。直接用暴力+滚动数组,试试就去世。
且不能使用完全背包问题的优化方法,因为没法求出一组数除最后一位的最大值。
得使用二进制优化技巧(题目已经提示了)
二进制优化
思路
假设s = 1023,要枚举s
真的要一个个遍历1023次吗?
其实可以使用二进制方法将其分为(打包)成10组
整个s就只要枚举10次,而在每组里面,成01背包问题(只能选一次)
效果
能把DP中的一层 for 从 O(N) 降成 O(logN)
就是说,从 O(NVS) 到 O(NVlogs)
重点:分组
如何分?
比如,200,能分成:[1, 2, 4, 8, 16, 32, 64, 73]
128不能要,因为[1, 2, 4, 8, 16, 32, 64]就已经到127了, 127 + 128 = 255 超200了
一般规律
s 分成 [1, 2, 4, 8, 16, 32, 64…2^k + c]
- 其中2^k是小于s的最大二次幂
- c严格小于2^(k + 1)
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; j >= v[i]; 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, tmpS int
v, w = []int{0}, []int{0}
cur = 0
)
fmt.Scanln(&N, &V)
for i := 1; i <= N; i++ {
fmt.Scanln(&tmpV, &tmpW, &tmpS)
k := 1
for k <= tmpS {
cur += 1
v = append(v, k * tmpV)
w = append(w, k * tmpW)
tmpS -= k
k *= 2
}
if tmpS > 0 {
cur += 1
v = append(v, tmpS * tmpV)
w = append(w, tmpS * tmpW)
}
}
N = cur
ans = cal(N, V, v, w)
fmt.Println(ans)
}