算法笔记：0-1背包问题

 

n个商品组成集合O，每个商品有两个属性vi（体积）和pi（价格），背包容量为C。

求解一个商品子集S，令

优化目标 

1. 枚举所有商品组合

共2^n - 1种情况

2. 递归求解

KnapsackSR(h, i, c)：在第h个到第i个商品中，容量为c时的最优解

P1：选择商品i

P2：不选择商品i

取二者最大值P = max{P1+pi, P2}

3. 带备忘递归

4.  动态规划

 

 时间复杂度 O(n*C)

 

最优子结构性质：

（1）问题的最优解由相关子问题最优解组合而成

（2）子问题可以独立求解