HDU1864 - 最大报销额
最大报销额 这道题有两个需要注意的地方：一是题目说的“每项”其实是“每类”，也就是A类,B类和C类，而不是每个物品......(这题目表述有问题啊！)；二是在计算时要将所有的数据扩大100倍然后再转为int，计算出最后结果后再缩小为原来的倍率，否则无法用钱数来做背包(浮点数无法作为数组下标)。
Read moreHDU2546 - 饭卡
饭卡 一道01背包的题目，特殊之处在于要先拿出5元用来买最贵的东西，剩下的钱即为背包，然后就是普通的01背包了。
Read morePOJ1384 - Piggy Bank
Piggy Bank 完全背包的经典问题，只要把状态转移方程的max改为min，同时将dp[0]设为0，其余则设为INF即可( 因为要求是否能装满 )
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 moreHDU2602 - Bone Collector
Bone Collector 一道01背包模板题，套模板即可
Read moreURAL - 1244 Gentlemen(01背包+记录路径)
URAL - 1244 Gentlemen 一道01背包的题目，只不过这一次不是用01背包来求最大值或最小值，而是将背包填满。这只需要将数组dp[]的dp[0]设为0，将其他设为 -∞即可（原因：这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。） 难点在于记录路径，同时处理多个解的情况。一开始我也想不到要怎么处理多个解的情况(总不能做两次dp..
Read moreAizu - ALDS1_1_D-Maximum Profit（转化思想+DP）
Aizu - ALDS1_1_1_D (这貌似是个日本的oj？名字叫aizu有点奇怪呢hhhh)
Read more