存档

2012年4月 的存档

0-1背包

2012年4月30日 3 条评论

---

四月份还没写,不能这么荒废了呀,赶紧水一篇吧,哈哈。前些日子回顾了DP的一些基础,就做一下整理吧,从0-1背包开始。

本节回顾0-1背包的基本模型,关于它的实现有很多种写法,这里对不同实现做个简单列举,主要是写代码练手了,主要有以下几方面内容:

==0-1背包问题定义 & 基本实现

==0-1背包使用滚动数组压缩空间

==0-1背包使用一维数组

==0-1背包恰好背满

==0-1背包输出最优方案

========================================

0-1背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品,每种物品只有一个,想计算一下最多能放多少价值的货物。

DP的关键也是难点是找到最优子结构和重叠子问题,进而找到状态转移方程,编码就相对容易些。最优子结构保证每个状态是最优的,重叠子问题也即n状态的求法和n-1状态的求法是一样的;DP在实现上一般是根据状态转移方程自底向上的迭代求得最优解(也可以使用递归自顶向下求解)。

回到0-1背包,每个物体i,对应着两种状态:放入&不放入背包。背包的最优解是在面对每个物体时选择能够最大化背包价值的状态。0-1背包的状态转移方程为


f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }

阅读全文...