一个算法一个例题教会你算法---0-1背包问题

动态规划

0-1背包问题

0-1背包问题就是求在有重量限制的情况下如何装入价值最大的物品。

啥也别说，直接看题：

现在有四个可以放的物品，w代表重量，v代表价值。

step1：
我们列一个背包重量 j 从0到5的表格，纵轴 i代表每个物品的序号。

step2：
j=0时，背包载重为0不能放下任何物品，第一列我们直接先全部填0.

step3：
在j=0时，我们为了方便选择将第一列全部填0。

接下来，我们一行一行来填数值。

i=1，代表现在只有第一个物品可以装入书包。（w=2,v=3)

当j=1时，书包载重小于物品重量，因此i=1，j=1时总价值为0。

因此，我们填0.

step4：
接下来，j=2。可以装入第一个物品，因此现在总价值为3.

后继j=3,j=4,j=5，同理。因为，我们现在只考虑第一个物品入背包的情况，所以最大价值都为3.

step5：
再来看第二行，i=2。

此时，前两个物品我们都可以选择，然后再看背包重量的变化。

** step6：**
后继操作以此类推，我们就可以得到最终的最大价值为13