写一些关于DP的知识
1、任何的01背包，都可以把价值V和容量W互换，就是说有两种方法可以解背包，比如将n个物品放入容量为W的背包，问能获得的最大价值。可以转化为，将n个物品放入容量为V（V为所有物品的价值总和）的背包，能获得的最小价值（对应于原问题中的最小重量）是多少。所以，当某个方向的问题不可解时（比如状态太多，或者状态下标要用浮点数表示什么的）就可以将其用另一个方向做，典型的问题是hdu2955抢银行。
2、有的时候我习惯用dp值为-1代表某个状态不可达，因为有些时候怕如果赋值为正负无穷的话会运算越界，但是如果设置不合法dp值为-1的话，一定要确保正常的dp值不能为-1。
3、打印解路径。可以用两个一维数组打印（一个数组是dp数组，另一个是决策数组s，s[i]记录dp[j]是怎么转移来的），这个时候需要背包是恰好装满时候的背包，如果是可以不装满的背包，无法用两个一维数组来打印解路径，需要至少用一个二维数组，但是其实任何不装满的背包都可以按照装满背包的方法解，最后再检查一遍所有的合法值就行了。
Comments