目录

一、算法思想

二、解题步骤?

三、神奇的兔子序列?

（一）问题

（二）递归公式

（三）以求解F(6)为例?

（四）代码

四、01背包问题

（一）算法思想?

（二）举例

1. 有3种物品

2. 背包问题网格

3. 初始化第一列

4. 吉他行

5. 音箱行?

6. 电脑行

7. 总结

（三）核心代码

（四）完整代码

• 动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解成若干子问题，自顶向下求解各子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原问题分解为若干子问题然后自底向上，先求解最小的子问题，把结果存储在表格中，再求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计数，从而提高算法效率。

（1）分析最优解的结构特征

（2）建立最优值的递归式

（3）自底向上计算最优值，并记录

（4）构造最优解

前两个月都是1对兔子，从第3个月开始，当月的兔子数等于前两个月的兔子数，求解第n个月的兔子数量？

?

• 利用动态规划求解的时候，记录结果，重复问题只需要求解依次即可

• 用数组表示从下标为0到的物品里任意选取，然后放进容量为的背包中，背包所能装入的最大价值。

对于一个物品i，要么能放入背包，要么不能放入背包：

• 第一种情况：物品的重量大于背包容量的时候，此时物品不能放入背包中，那么需要从剩下0到个物品中任意选取放入背包中，此时背包所能装入最大价值为。
• 第二种情况：物品的重量小于背包容量的时候，此时物品能放入背包中，但是可以选择将物品不放入背包或者放入背包。第二种情况又分以下两种：
• 1.选择不将物品放入背包的时候，那么从剩下的0到个物品中任意选取价值大的物品放入背包中，此时背包所能装入最大价值为。
• 2.选择将物品放入背包的时候，需要先将物品放入背包，那么背包剩余容量为，
• 此时从剩下的0到个物品中任意选取价值大的物品放入背包中，背包所能装入最大价值为
• 那么物品最大价值为：

所以背包所能装入最大价值为：

?

• 背包容量为0，意味着吉他，音箱，电脑都不能装入背包，所有此时背包最大价值均为0?

?1.??第2个单元格表示背包的容量为1磅。吉他的重量也是1磅，这意味着它能装入背包！

2. 之后背包容量为2磅，3磅，4磅也能装下

?3. 表明若一个背包容量为4磅，可在其中装入的商品的最大价值为1500美元

?

• 更新最大值：表明若一个背包容量为4磅，可在其中装入的商品的最大价值为3000美元

?

?