动态规划-01背包问题

一、背包问题描述

当下有一个容量为V的背包，并且有n个物品分别具有体积v[i]和价值w[i]。那么，在这个背包中最多能装入总价值是多少的物品？

由于每种物品只有一个 ，也就是物品只有拿和不拿 两种状态，所以这个问题被称为01背包问题。

二、贪心和反例

这类问题是解决方法中最常用的方式就是运用贪心算法。具体来说，在选择物品时我们最常考虑的是高价值或者是物美价廉的选择方式；然而尽管如此 我们依然能够轻易地构造出反例来证明这种方法并不总是适用的

举例说明如下：假设背包容量设定为10单位，在此情况下共有三个待选物品可供选择。这些物品的各个维度参数分别为：各具体积分别为6、5和5单位；各具价值分别为10、8和8单位。这种反例表明这两种贪心策略均不适用。具体而言，在选择时优先考虑总价值最大的那个（即值为10的那个）会导致无法后续获取其他任何物品；同时，在选择时优先考虑总体积最小的那个（即值为6的那个）也会导致整体收益损失明显。因此，在上述特定情况下应用的价值最优贪心策略也不奏效。

事实上连现有的所有贪心策略都不奏效。
看上去简单的问题却并不易于解决。
诚然这个问题长期困扰着计算学家
直至上世纪六十年代动态规划算法才真正地解决了这一难题。

三、动态规划（dynamic program