一、问题描述
有n个物品，第i个物品的体积为ci，价值为wi，还有一个容积为v的背包，现在往背包中装物品，怎样才能使得背包内的物品价值最大。
二、分析思路
步骤1：用函数的形式来表示题目结果。
设f(x,v)=y，表示有x个物品，容积为v的背包的最大价值。那么本题要求的便是f(n,v)。
步骤2：分析递推情况。
递推情况分析主要是考虑一般的情况，即f(i)与f(i-1)等之间的关系。
那么本题我们考虑在背包容量限制为v的前提下，有i个物品和i-1个之间的关系。
假如我们现在已经知道f(i-1,v)的值即要装i-1个物品达到的最大值，接下来分析是否要装第i个物品，只有两种情况装或不装。如果不装第i个物品的话，那么体积限制还是v，最大价值是f(i-1,v)，如果要装第i个物品，那么i-1个物品的体积限制就应该是v-ci,最大价值应该是i-1个物品的最大值加上第i个物品的价值即f(i-1,v-ci) + wi
综上，我们得到如下的递推公式：
f(i, v) = max{ f(i-1, v), f(i-1, v-ci) + wi }
步骤3：算法实现。
如您对该算法感兴趣，“算法与编程之美”公众号将为您做后续讲解。
三、总结
本文给大家介绍了利用动态规划算法求解01背包的问题，您掌握了吗？背包问题除了01背包之外还有很多其他类型的变种，如完全背包等，后续博客将逐一的介绍。
