前言

最近学习了0-1背包问题,看了很多博文,讲的都不是很清楚。自己写一个以便以后复习。


一、0-1背包问题是什么?

给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问:应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

二、题解思路

1.原理

0-1背包问题属于动态规划的经典问题,动态规划与分治的区别在于动态规划有一个记录表,不用每次从最底部开始递归,节省了很多计算量。

2.记录表

横坐标j表示背包容量。

纵坐标i表示的是背包中物品的编号,且背包中只能装编号及以前的物品。

表格中的数据表示的是最大价值。

3.递推式

① j<w(i) V(i,j)=V(i-1,j)

② j>=w(i) V(i,j)=max{ V(i-1,j),V(i-1,j-w(i))+v(i) }

第一个递推式很浅显易懂,主要是第二个,我弄了半天才明白,看别人的都说第I件拿了和不拿间选一个大的值,我被绕进去了,想着这怎么算,肯定拿了比不拿价值更高啊。

但是V(i-1,j-w(i))+v(i)并不是在V(i-1,j)的基础上拿一个价值为v(i)的物品所得的价值,而是上一行记录表中容量为j-w(i)的价值,加上当前拿的物品的价值,得出来的价值与当前记录上一行的价值比较,这样比较出来的才是当前最大的值。