点这里查看
讨论 / 求高速解法，2000ms以内
rock3334280 2009-07-15 06:28:00
点我顶贴 收藏 删除
虽然a了 但4000++ms很危险

后三个点 擦着900过的

我的是很朴素的解法

for i:=1 to n do

for j:=v downto w[i]

for k:=1 to min(v div w[i],m[i]) do

{更新dp数组}

请教 更优化的解法

#1 wish@2009-07-14 23:35:00
回复 删除
多重背包问题

有 O(MNlgM) 和 O(MN) 两种方法

第一种是分拆物品

第二种是利用单调队列进行优化

#2 rock3334280@2009-07-15 00:29:00
回复 删除
拆分？

就像 背包就讲 里说的 拆二进制？

#3 wish@2009-07-15 02:35:00
回复 删除
对,单调队列的稍微麻烦些

你可以参考 2009 wc 的某篇论文

#4 rock3334280@2009-07-15 06:28:00
回复 删除
谢过
查看更多回复
提交回复