动态归纳法求0-1背包问题

面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入同一物品多次。把物品随机排成一排,标记为1、 2、 3……，从1号物品开始依次判断是否装包，面对当前物品有两种情况：该物品的重量大于背包的容量,装不下,只能选择不装该物品的重量小于背包的容量，可以装下，但是否要装,需要进一步判断,因为可能存在这种情况:要装该物品,就必须拿出之前装的一个物品,可能会出现如下情况:1.[拿掉之前的一个物品并装进当前物品后背包的总价值]<[不拿掉之前的物品且不装当前物品背包的总价值] ;2.[拿掉之前的一个物品并装进当前物品后背包的总价值]>[不拿掉之前的物品且不装当前物品背包的总