UVA - 12563 Jin Ge Jin Qu hao
Jin Ge Jin Qu hao 一道01背包，虽然t<=1e9，但实际上t不会超过180 * n + 678。
Read more洛谷P1417 烹调方案
P1417 烹调方案 依然是01背包。这道题跟之前HDU的那道merchant很像，都是要先算一个不等式，再根据这个不等式进行排序，然后再进行01背包。具体而言，是要解下面这个不等式： a1 - (t0 + c1) x b1 + a2 - (t0 + c1 + c2) x b2 > a2 - (t0 + c2) x b2 +a1 - (t0 + c1 + c2) x b1 ==> b2 c1 < b1 c2 具体代码如下: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define mst(a,b) memset(a,b,..
Read more洛谷P1855 榨取kkksc03
P1855 榨取kkksc03 一道01背包模板题，但多了一个维度。
Read moreHDU3466 - Proud Merchant
Proud Merchant 这道题最难搞的地方在于如何处理“小于qi时不能买”这一要求。苦思冥想许久，依然不知如何解决，于是只好去看题解...... 这道题的做法是首先将“商人”按照q-p排序，然后再进行01背包。为什么是按照q-p排序呢？假设有两件物品A,B,他们对应的p,q分别是p1,q1和p2,q2。如果这两件东西都要买，那么，如果先买A，就至少需要p1 + q2的钱才能把两件东西都买到；如果先买B，就至少需要p2 + q1的钱才能把两件东西都买到。为了买到尽可能多的东西，获得尽可能大的价值，就应该按照代价小的方式来买。也就是说，假如先买A比先买B所需的代价更小，就有p1 + q2 < p2 + q1，即q1 - p1 < q2 - p2。 代码如下: #include <..
Read moreHDU1864 - 最大报销额
最大报销额 这道题有两个需要注意的地方：一是题目说的“每项”其实是“每类”，也就是A类,B类和C类，而不是每个物品......(这题目表述有问题啊！)；二是在计算时要将所有的数据扩大100倍然后再转为int，计算出最后结果后再缩小为原来的倍率，否则无法用钱数来做背包(浮点数无法作为数组下标)。
Read moreHDU2546 - 饭卡
饭卡 一道01背包的题目，特殊之处在于要先拿出5元用来买最贵的东西，剩下的钱即为背包，然后就是普通的01背包了。
Read moreHDU1171 - Big Event in HDU
Big Event in HDU 这道题是让我们将设备根据价值尽可能地平均分成两半，其实就是把设备的价值总和平分成两个部分，然后以此为背包，将这个背包尽可能填满。因为这里的“体积”和“价值”都是设备的价值，所以其实就是求价值的最大值。题目还要求输出时，大的在前面，小的在后面，这可以利用整除的特性做到，因为一个整数a整除2得到的结果一定是小于或等于a/2(非整除)的。 代码如下： #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <climits> #include <algorithm> using namespa..
Read morePOJ3624 - Charm Bracelet
Charm Bracelet 一道01背包模板题，套模板即可。
Read moreHDU2955 - Robberies
Robberies 依然是01背包，但这次的有点特殊。特殊之处在于，背包的总体积是可以获得的钱的最大值( 如果是以概率为背包也不能枚举啊23333 )，然后用动态规划求得获得该钱数被抓的最大概率( 如果在最大概率的情况下都不会被抓，那就肯定不会被抓 )。
Read moreHDU2639 - Bone Collector II
Bone Collector II 这道题与Bone Collector的不同之处在于，这道题求的是第k优解，而非最优解。那应该怎么做呢？ 首先，01背包的核心方程式dp[j] = max(dp[j] , dp[j - w[i]] + v[i]) ,也就是说，每一个新状态都是由dp[j]或dp[j - w[i]] + v[i]转移来的。我们首先用一个数组a[]和一个数组b[]将这两个状态存起来，然后再循环求得第k优解。这个过程有点像是，一个年级有两个班，我需要知道全年级的前十名是谁，那我就可以通过得到第一个班的前十是谁和第二个班的前十是谁来求得全年级的前十。 代码如下： #include <iostream> #include <cstdio> #include <cs..
Read more