一、背包问题描述：
有N种物品和一个重量为M的背包，第i种物品的重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量，且价值总和最大。
二、解决方法：
1、贪心算法：贪心算法基于的思想是每一次选择都作当前最好的选择，这样最后的结果虽然不一定是最优解，但是也不会比最优解差很多。
举个例子说明可能好懂一些：一帮基友去聚餐，菜是一份一份上的，我每一次夹菜都只夹牛肉/海鲜吃，可能到最后我吃的牛肉/海鲜很多，但不一定代表我吃掉的东西的总价值最高，但是相对来说价值也很高了～
换句话说，对于贪心算法，其核心在于设定一个标准让我们去贪。回到这个问题，这个标准就有三种设法了：1、价值最高的先装进背包；2、重量最低的先装进包；3、性价比（价值和重量的比值）最高的先装进背包。我在这里用的是第三种方法，用快排作了排序。
在 装的过程中要注意的就是，当前物品能不能放进背包。这个是需要考虑的。因为背包问题也有好几种，如：0-1背包问题（每种物品只能拿一次）、完全背包问题 （每种物品都能拿无限次）、多重背包问题（每种物品都有一定的数量可以拿）。所以在不同情况下贪心算法的一些细节设计也是不一样的，这个需要自己考虑。
2、动态规划算法：贯穿动态规划算法的就是状态和状态转移方程这两个东西，而要得到这两个东西需要我们把我们的问题分解为更小的子问题，通过分析子问题去获得。
那么回到我们这个问题，由于每次装东西进背包，我们只考虑能否装进，以及是否当前状态下的最优选择，也就是说，我们需要用背包的容量去设计一个数组，存储每一单位个容量的最大价值是多少，以此类推，获得背包容量下的最大价值是多少。这样说可能说不清楚，看看下面的代码吧～
三、代码：
1、贪心算法：
2、动态规划算法：
3、可能有人会需要，在解决这个问题的情况下我修改的快排
