最近在看 dd_engi的背包九讲，于是也上poj找点背包问题的题目来做，于是找到了poj1742_coin
http://acm.pku.edu.cn/JudgeOnline/problem?id=1742
题意就是有若干种硬币，每种硬币数量有限。求可以组合出多少面值？
然后根据《背包九讲》，这就是个经典的多重背包问题了，然后就先写基本算法：
第i种硬币面值是a[i]，数量是c[i]，就把这题转换成有（c[0]+...+c[i]+...＋c[n]）个物品的0－1背包问题于是时间复杂度O(n*m*c)，然后这种算法TLE
于是回头继续读《背包九讲》，将背包按照二进制分解，例如某个物品，c[i]=13，就将这种物品分别分成 价值分别为 1*a[i]，2*a[i]，4*a[i]，6*a[i] 的四件物品，于是时间复杂度优化到O(n*m*logc)，结果竟然还是TLE……
再次读《背包九讲》：“多重背包问题同样有O(VN)的算法。......由于用单调队列优化的DP已超出了NOIP的范围，故本文不再展开讲解。"于是开始四处搜索解题报告，找到了“楼教主”的有关文章，还是读不懂，无奈只好直接找别人的代码来学习，这才明白一点：
将这个 多重背包问题 转化为 完全背包问题，也就是每个物品都有无限个，但是在循环过程中用一个数组记录 ：某种硬币i使用的次数，如果使用次数超过c［i]，则停止循环。恩，大意如此，时间复杂度就是O(n*m)，终于AC。
不过楼教主的＊＊＊bit＊＊＊方法还是不懂，最后说一句：做男人真不容易
Read full article from 多重背包问题 的 O(VN)的算法_曙光_新浪博客
No comments:
Post a Comment