Category OI

背包问题是信息学奥赛中最经常考的动态规划形式，而01背包又是背包问题的基础。除此之外，背包问题还分为完全背包、多重背包等。 01背包定义如下： 对于1个容积为v的背包和n个物品，这些物品分别有自己的体积Vi，和价值Pi，我们需要有一种算法在背包可以容纳的情况下使装入的物品价值最大。此时n个物品不一定全部放入，背包也不一定装满。 与完全背包不同的是，01背包中是n个物品，而完全背包是n种物品，每种物品可多次放入。 这样的问题为什么不用搜索解决呢？ 显然，如果搜索可以完美解决这样的问题，我们自然也就不需要用更好的算法来解决问题了。 通过分析问题，我们可知，对于每个物体都有放入背包和不放入背包两种情况，如果我们使用传统的搜索算法解决这个问题，那么时间复杂度为O(2^n)，数据大了难免超时。 何为动态规划： 动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。继续分析，我们可以通过递推的方式解决该问题，从问题分析出递推式的方法，便是动态规划。 如何用动态规划高效地解决01背包问题？ 这是一个01背包常见的递推式 f[i][j]=max(f[i-1][j],f[i-1][j-Vi]+Pi) 其中，i从1到n，j从1到v，条件为j>=Vi 许多人与我一样，在第一次看到这个递推式的时候都十分困惑，全然不知它的含义。 实际上，f[i][j]就是我们在写动态规划程序时所需要开的一个数组，f[i][j]表示放入前i个物品（包含i，但这前i个物品不一定完全放入），背包容积为j时，背包内物品价值和的最大值。 这样，f[i-1][j]显然就是不考虑放入编号为i的物品的情况下背包内物品的最大价值和，而f[i-1][j-Vi]+Pi，便是在只考虑放入前i-1号物品且背包容积为j-Vi时，背包内物品的最大价值和，再放入编号为i的物品，因此加上Pi，也就得到了f[i][j]，即放入前i个物品，背包容积为j时背包内物品的价值的最大值。 对于这个算法，在C语言中通常采用两层for循环解决，以下为C++写法。大家可以根据题目自己修改以符合题目要求。 该方法的时间复杂度为O(n*v)…