题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1171
题目大意
有N种物品,每一种物品有一个价值value和数量num,要把这N种物品分成两份,要求使两份的差尽量小并且保证第一份大于第二份。
思想
是一个背包DP,让两份的差尽量小,我们以可将总价值平分,作为背包容量,这样两份都会尽可能的靠近sum/2,这样差会最小。
有了大概的思路,我们就开始表示状态和划分阶段。
背包DP的基础是01背包,意思就是每种物品有一件,只需要考虑放不放。而实际上本题为多重背包,但是可以转化为01背包去解。
01背包:背包容量为V,我们用dp[i][j]表示前i件物品放入容量为j的背包中所产生的最大价值。
那么第i件物品放与不放,只与前i-1件物品有关。① 如果放第i件物品,那么就是前i-1件物品放入了j-value[i]的背包内,因为要给第i件物品腾出value[i]的空间。同时,总价值要加上第i件的价值。即dp[i][j]=dp[i-1][j-value[i]]+value[i];② 如果不放,则不需要给第i件物品腾出空间,那么背包容量没变。那么dp[i][j]=dp[i-1][j]。
又因为要最大,所以dp[i][j]=max{dp[i-1][j],dp[i-1][j-value[i]]+value[i]}
代码
1 |
|
后记
对于DP不同的种类划分,似乎很多都是根据不同的状态表示而分的。
对于背包DP来说,很多问题都可以转化为01背包去解决,但是会比较低效,所以有相应的优化算法。