0— 1 背包动态规划解决问题
一、问题描述：
二、总体思路:
过程：
a) 把背包问题抽象化（X
1
,X
2
，
ⅆ , Xn,其中 Xi 取 0 或 1，表示第 i 个物品选或不选）,V
i
表示第 i 个物品的价值， W
i
表示第 i 个物品的体积（重量)；
b） 建立模型， 即求 max(V
1
X
1
+V
2
X
2
+…+VnXn);
c） 约束条件,W
1
X
1
+W
2
X
2
+…+WnXn<capacity；
d） 定义 V(i,j):当前背包容量 j，前 i 个物品最佳组合对应的价值；
e) 最优性原理是动态规划的基础，最优性原理是指“ 多阶段决策过程的最优决策序列具
有这样的性质：不论初始状态和初始决策如何， 对于前面决策所造成的某一状态而言,其后
各阶段的决策序列必须构成最优策略" 。判断该问题是否满足最优性原理， 采用反证法证明:
假设(X
1
,X
2
,…,Xn）是 01 背包问题的最优解,则有(X
2
,X
3
，ⅆ , Xn）是其子问题的最
优解，
有 n 个物品，它们有各自的重量和价值，现有给定容量的背包,如何让背包里装入的物品具
有最大的价值总和?
根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、
找大问题与小问题的递推关系式、填表、寻找解组成）找出 01 背包问题的最优解以及解组
成，然后编写代码实现。
三、动态规划的原理及过程：
number ＝4，capacity ＝7
i 1 2 3 4
w（重量) 3 5 2 1
v(价值）
9 10 7 4
原理：
动态规划与分治法类似， 都是把大问题拆分成小问题， 通过寻找大问题与小问题的递推
关系,解决一个个小问题,最终达到解决原问题的效果.但不同的是,分治法在子问题和子子问
题等上被重复计算了很多次，而动态规划则具有记忆性,通过填写表把所有已经解决的子问
题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约
了时间,所以在问题满足最优性原理之后， 用动态规划解决问题的核心就在于填表，表填写
完毕，最优解也就找到.
