背包练习小集合

1月 15th, 2013 1,875 留下评论 阅读评论

练习DP就从背包开始吧,比较简单一些,因为套路基本都差不多,适合入门。做提前,推荐上网搜一下《背包九讲》读个一遍就大致了解背包题了,顺便再次ym下dd大牛…做了不少zoj里的背包题目,大概估计下来,但背包大小 <= 10w的情况下,一般都不会超时。

0-1背包

poj 3624 最基础的0-1背包

zoj 3258 要考虑剩下的背包空间,然后按贪心算法用水去装填

zoj 3264 已经有点分组背包的意思了,不过只要简单处理下二选一即可;要注意w = 0的情况,两次dp[m] = max( dp[m], dp[m – w] + v )会出错,用临时变量记录dp[m]的值做计算

zoj 3305 要排序后去重,即真包含的情况

zoj 3049 先贪心后背包,即用哪几个特殊物品直接卖掉来凑这个卷轴钱,使得损失最小

zoj 2822 求一个数由不同质数求和而成的种数。一开始没用01背包直接DP一直过不了“不同”质数这一条件。

完全背包

zoj 1666 计算钱的凑法

zoj 2014 完全背包取最小值

zoj 2224 多次的完全背包

zoj 2955 完全背包不难,但是背包值太大,看网上用的抽屉原理优化(原理没咋看懂…看过就忘…)

多重背包

多重背包比较复杂,一般用背包九讲上说的O( V * ∑n[i] )的方法也足够了。

当dp数组存的是0或1的情况下(即只考虑这个背包值是否可以达到,而不保存某最优值),可以模拟完全背包然后用个数组保存背包值->物品用的次数就可以了,这样简单很多。

zoj 1149 就是看一堆数是否能凑到所有数和的一半

zoj 2189 计算钱的凑法,硬币数量有限,要求硬币数量最少,保存dp路径

zoj 2156 也是计算钱的凑法,不过硬币数量有限而且要取硬币数量最多的表示方法(并不是只用小的货币就一定是最多的硬币数),还要保存dp的路径

分组背包

zoj 2972 刘翔跨栏题

zoj 3450 按照坐标原点的射线分组,最大公约数

综合背包

zoj 3164 集合0-1背包、完全背包、多重背包、分组背包…不过0-1背包算是多重背包的一个特殊情况吧

Categories: 数据结构和算法 标签:,
  1. hzqtc | #沙发
    1月 15th, 2013 21:33

    orz to death!
    这必须是明年横扫offer的节奏了。

    • 普通DP都不会给跪了!!!今年下半年求罩!