文章目录
-
- 1 背包问题定义
- 2 回溯法
-
- 2.1 回溯法的设计思想
- 2.2 回溯法求解0/1背包问题
- 2.3 算法步骤
- 2.4 代码实现
- 2.5 实验结果
-
- 2.5.1 回溯法求解背包问题的搜索树
- 2.5.2 搜索树生成过程
- 2.5.3实际输出：
- 2.6 回溯算法的效率分析
- 3 贪婪算法
-
- 3.1 贪婪法的设计思想
- 3.2 贪婪法解决部分背包问题
-
- 3.2.1 算法设计：
- 3.2.2 实验结果
- 3.3贪婪算法解决0/1背包问题
-
- 3.3.1 算法设计
- 3.3.2 实验结果
- 4 动态规划算法
-
- 4.1 动态规划的设计思想
- 4.2 动态规划法求解0/1背包问题
- 4.3 算法步骤
- 4.4 代码实现
- 4.5 优化算法
- 4.6 实验结果
- 5 动态规划法和贪婪法对比
- 6 总结
1 背包问题定义
给定一个载重量为M的背包，还有n个重量为wi,价值为pi的物体，1<=i<=n,要求把物体装满背包，并且使得背包内物体的价值最大，这类问题称为背包问题。背包问题还可划分成两类，一类是0/1背包问题：物体不可分割，只能完整的装入背包，另一类是非0/1问题：物体可以分割成部分装入背包。本文将用三种算法求解背包问题，并进行对比，三种算法分别是：回溯法，贪婪法和动态规划法。
2 回溯法
2.1 回溯法的设计思想
回溯法在确定了解空间的结构后，从根结点出发，以深度优先的方式搜索整个解空间，此时根结点成为一个活结点，并且成为当前的扩展结点。每次都从扩展结点向纵向搜索新的结点，当算法搜索到了解空间的任一结点，先判断该结点是否肯定不包含问题的解（是否还能或者还有必要继续往下搜索），如果确定不包含问题的解，就逐层回溯；否则，进入子树，继续按照深度优先的策略进行搜索。当回溯到根结点时，说明搜索结束了，此时已经得到了一系列的解，根据需要选择其中的一个或者多个解即可。
回溯法解决问题一般分为三个步骤：
- 针对所给问题，定义问题的解空间。
- 确定易于搜索的解空间结构。
- 以深度优先的方式搜索解空间。
2.2 回溯法求解0/1背包问题
假设：xi是物体i被装入背包的部分，xi =0，1，当xi=0时表示物体i没有被装入背包；当xi=1时表示物体i被全部装入背包。根据问题的要求，可以构造下面的约束方程和目标函数：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}}{{\math…
于是问题可以归结为寻找一个满足约束方程（1），并使得目标函（2）达到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。回溯法搜索这个解向量X时，状态空间树是一个高度为n的完全二叉树，其节点总数是2^(n+1) -1.从根节点到叶子节点的所有路径，描述了问题解的所有可能状态。
首先约定：第i层的左儿子子树描述物体vi被装入背包的情况，右儿子子树描述物体vi未被装入背包的情况。
在状态空间树的搜索过程中，一方面可以通过约束方程（5）来控制不需要访问的节点，另一方面还可以利用目标函数（6）来进一步控制不需要访问的节点的个数。初始化时把目标函数的上界初始化为0，把物体按价值重量比的非增顺序排列，然后按照这个顺序搜索；尽量沿着左儿子节点前进，当不能沿着左儿子节点继续前进时，说明得到了问题的一个部分解。然后把搜索转移到右儿子子树。此时，估计这个部分解所能得到的最大价值，把该值和当前的上界进行对比，如果该值大于当前上界，就继续由右儿子树向下搜索，扩大这部分解，直到找到一个可行解。最后把可行解保存起来，用当前可行解的值刷新目标函数的上界，并向上回溯，寻找其他可行解；如果由部分解所估计的最大值小于当前上界，就丢弃当前正在搜索的部分解，直接向上回溯。
2.3 算法步骤
假设当前的部分解是{x0,x1,…,xk-1}，同时有：
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {{\mat…
式子（7）表示装入第k个物体之前，背包尚有空余的载重量，继续装入物体k之后，将超过背包的载重量。由此得到部分解{x0,x1,…,xk}，其中xk=0。由这个部分解继续向下搜索将有：
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {{\mat…
式子（8）表示，不装入第k个物体，继续装入k+1,k+2…k+m-1的物体，背包尚有空余的载重量，但是继续装入第k+m个物体之后，将超过物体的载重量。因为物体是按照价值重量比按非增顺序排列的，因此这个部分解还可以继续向下搜索。能找到的可能解的最大值不会超过：
∑ i = 0 k x i p i + ∑ i = k + 1 k + m − 1 x i p i + ( M − ∑ i = 0 k x i w i − ∑ i = 0 k + m − 1 x i w i ) × p k + m / w k + m ( 9 ) {{\mathop{ \sum }\limits_{{i=0}}^{{k}}{\mathop{{x}}\nolimits_{{i}}\mathop{{p}}\nolimits_{{i}}}}+{\mathop{ \sum }\limits_{{i=k+1}}^{{k+m-1}}{\mathop{{x}}\nolimits_{{i}}\mathop{{p}}\nolimits_{{i}}}}+{ \left( {M-{\mathop{ \sum }\limits_{{i=0}}^{{k}}{\mathop{{x}}\nolimits_{{i}}\mathop{{w}}\nolimits_{{i}}}}-{\mathop{ \sum }\limits_{{i=0}}^{{k+m-1}}{\mathop{{x}}\nolimits_{{i}}\mathop{{w}}\nolimits_{{i}}}}} \right) } \times \mathop{{p}}\nolimits_{{k+m}}/\mathop{{w}}\nolimits_{{k+m}}}(9) i=0∑kxipi+i=k+1∑k+m−1xipi+(M−i=0∑kxiwi−i=0∑k+m−1xiwi)×pk+m/wk+m(9)
如果当前搜索到当前结点，它的最大价值估计值小于当前目标函数上界，则放弃向下搜索，进行回溯。如果当前结点是左儿子子树结点，则转向相应的右儿子子树结点进行搜索；如果当前结点是右儿子子树结点，则退回父节点。
用回溯法求解0/1背包问题可以概括为以下10个步骤：
- 把物体按价值重量比按照递减的顺序排列。
- 把w_cur（当前背包物体的总重量）、p_cur（当前背包物体的总价值）和p_total（所有可行解的最大价值）初始化为0，解向量的各个分量初始化为0，搜索树的搜索深度k置为0 。
- 令p_est（当前部分解可能达到的最大价值的估计值） = p_cur，对满足k<=i<n的所有i，按照式子（8）（9）更新从当前的部分解可取的的最大价值估计值p_est。
- 如果p_est > p_total，转步骤5，否则转步骤8.
- 从vk开始把物体装入背包，直到没有物体可装入或者装不下物体vi为止，并生成部分解yk,…,yi，k<=i<n，刷新p_cur。
- 如果i>=n-1，则得到一个新的可行解，用可行解更新解向量X，更新p_total=p_cur。转步骤3，以便回溯到其他可行解，否则得到一个部分解，转步骤7
- 令k=i+1，舍弃物体vi，转步骤3，以便可以从物体v(k+1)继续装入。
- 当i>=0并且yi=0时，执行i=i-1，直到yi=1为止；即沿着右儿子分支节点方向向上回溯，直到回到相应的左儿子分支节点。
- 如果i<0,算法结束，否则转步骤10 。
- 令yi=0，w_cur=w-cur - wi，p_cur = p_cur - pi，k=i+1，转步骤3 。
2.4 代码实现
typedef struct {
float w; /*物体重量*/
float p; /*物体价值*/
float v; /*物体价值重量比*/
} Object;
Object ob[n]; /*n个物体下信息*/
float M; /*背包载重量*/
int x[n]; /*可能的向量解*/
int y[n]; /*当前搜索的解向量*/
float p_eat; /*当前搜索方向部分解的最大价值估计值*/
float p_total;
float w_cur;
float p_cur;
float knapsack_back(Object ob[],float M,int n,int x[]) {
float w_cur, p_total,p_cur,w_eat,p_eat;
int *y = new int[n+1];
for (int i = 0; i < n; i++) {
ob[i].v = ob[i].p /ob[i].w;
y[i] = 0;
}
merge_sort(ob, n); /*物体按照价值重量比的非增顺序排列*/
w_cur = p_cur = p_total = 0;
y[n] = 0;
k = 0;
while (k<=n) {
w_est = w_cur;
p_est = p_cur;
for (int i = k; i< n;i++) { /*沿着当前分支搜索*/
w_est += ob[i].w;
if (w_est<M) {
p_est += ob[i].p;
} else {
p_est += (M - w_est+ob[i].w)/ob[i].w * ob[i].p;
break;
}
}
if (p_est > p_total) { /*估计值大于上界*/
for (int i = k;i<n; i++) {
if (w_cur + ob[i].w <= M) { /*可装入第i个物体*/
w_cur += ob[i].w;
p_cur += ob[i].p;
y[i] = 1;
} else {
y[i] = 0; /*不能装入第i个物体*/
break;
}
}
if(i >= n-1) { /*n个物体已经全部装入*/
if (p_cur > p_total) {
p_total = p_cur; /*刷新当前上限*/
k = n;
for (int j = 0; j < n; j++) /*保存可能的解*/
x[j] = y[j];
}
} else
k = i+1; /*继续装入其他物体*/
} else { /*估计值小于当前上限*/
while ((k >= 0) && (y[k] != 0)) /*沿着右分支节点方向回溯*/
k = k-1; /*直到左分支节点*/
if (k<0) break; /*到根节点，则结束*/
else {
w_cur = w_cur - ob[k].w;
p_cur = p_cur - ob[k].p;
y[k] = 0; k += 1;
}
}
}
delete y;
return p_total;
}
2.5 实验结果
输入：物体数量为5，背包载重量为50，背包的价值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理论上输出：背包最大价值139，装入背包的物体为（0，1，1，1，0）。
2.5.1 回溯法求解背包问题的搜索树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G2Evpl6c-1580817786560)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107174612211.png)]
2.5.2 搜索树生成过程
- 开始时，目标函数的上界p_total初始化为0，计算从根节点开始搜索所取得的最大估计值p_est=159, 大于p_total，因此向下生成节点1，2，3，4，得到部分解（1，1，1，0）。
- 结点4是右儿子分支结点，于是估计从结点4开始向下搜索可取得的最大值p_est=151.5，大于p_total，因此继续向下搜索生成结点5，得到最大价值129，更新p_total=129，将可行解=（1，1，1，0，0）保存在解向量X中。
- 由叶子结点5继续搜索，估计可能取得的最大值为129，不大于p_total，因此向上回溯k–，直到yk=1到达结点3，并生成相应的右儿子分支结点6，得到部分解（1，1，0）。
- 计算从结点6开始搜索可取得的最大价值估计值p_est=155，大于p_total，因此向下继续搜索生成结点7、8。并生成最大价值p_cur=135，取得的可行解为（1，1，0，1，0），并更新p_total = p_cur=135。同时用这个可行解更新解向量X中的内容。
- 由结点8继续搜索，计算其最大价值估计值为135，不大于p_total，因此向上回溯，直到yk=1，回到结点7，并生成相应的右儿子分支结点9，得到部分解（1，1，0，0）。
- 计算从结点9搜索所取得的最大价值估计值为137.5，大于p_total=135，因此继续向下搜索生成结点10，得到最大价值p_cur=130，小于p_total的值，因此p_total和解向量X均未更新。因为结点10是左儿子结点，因此向前回溯后生成其相应的右儿子分支结点11，得到最大价值为85，小于p_total的值，因此p_total和解向量X均未更新。
- 由叶子结点11继续搜索，计算其最大价值估计值为85，小于p_total，因此沿着右儿子分支结点的方向向上回溯，直到结点2，生成其相应的右儿子分支结点12，得到部分解（1，0）。
- 计算从结点12向下搜索可取得的最大价值估计值为190，因此向下搜索生成结点13，14，15。得到最大价值为134，小于p_total，因此解向量X和p_total值均未更新。
- 由叶子结点15继续搜索，计算最大价值估计值为134，小于p_total，因此沿着右儿子分支结点方向向上回溯，到达结点13，生成其对应的右儿子分支结点16，由于结点16是右分支结点，计算其最大价值估计值为129，小于p_total ，因此沿着右儿子分支结点向上回溯，到达结点13，生成其对应的右儿子分支结点17，计算从结点17继续搜索可取得的最大价值估计值为140，因此可以沿着结点17向下搜索，生成结点18，19。得到的最大价值p_cur为90，小于p_total，因此解向量X和p_est均未更新。
- 由叶子结点19继续搜索，计算可取得的最大价值估计值p_est为90，小于p_total，因此沿着右儿子分支结点方向向上回溯，直到结点18，生成其相应的右儿子结点20，计算从结点20开始搜索可取得的最大价值估计值p_est=115，小于p_total，因此继续向上回溯，回到结点1，生成其相应的右儿子结点21。计算从结点21继续搜索可取得的最大价值估计值为180，因此继续向下搜索生成结点22、23、24、25。得到最大价值为139，大于p_total，因此更新p_total=139，得到可行解（0，1，1，1，0），用该可行解更新解向量X。
- 由叶子结点25继续搜索，计算可取得的最大价值估计值为139，不大于p_total，因此向上回溯回到结点24，生成其相应的右儿子分支节点26，计算从结点26搜索可取得的最大价值估计值为131.5小于p_total，因此继续向上回溯，回到结点23，生成其对应的右儿子分支结点27，计算从结点27搜索可取得的最大价值估计值为115小于p_total，因此继续向上回溯，回到结点22，生成其对应的右儿子分支结点28，计算从结点28搜索可取得的最大价值估计值为132小于p_total，因此继续向上回溯，回到结点0.算法结束。
2.5.3实际输出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HfHbqeZw-1580817786561)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107202953581.png)]
实验证明，回溯法可以求得0/1背包问题的最优解，但是它的时间复杂度和空间复杂度在最坏的情况下为O(2^n)。
2.6 回溯算法的效率分析
回溯算法的效率和以下几个因素有关：
- 生成节点所花费的时间
- 计算约束方程所花费的时间
- 计算目标函数的界所花费的时间
- 所生成节点的个数
回溯算法的运行时间取决于搜索过程中它生成的结点数。不同的搜索方式所生成的结点数是不同的。用回溯算法求解背包问题时，最坏的情况下，所搜索的结果是一棵满二叉树，时间复杂度为o(2^n)，每次还要对是否将n个物体装入背包进行比较，时间复杂度为O(n)， 因此最坏情况下回溯算法是时间复杂度是O(n*2^n)。
3 贪婪算法
3.1 贪婪法的设计思想
贪婪法一般由一个迭代的循环组成，在每一轮循环中，通过少量的局部的计算，寻找出一个局部最优解。因此它是通过一步步地寻找局部最优解来试图建立问题的最终解。贪婪法的每一步的工作都增加了部分解的规模，每一步的选择也都极大增长了它所希望实现的目标函数。正因如此，在很多实例中，利用贪婪算法所产生的局部最优解最终都能建立问题的全局最优解。
贪婪法有两个很重要的性质：
-
贪婪选择性质
所谓贪婪选择性质，是指所求问题的最优解可以通过一系列局部最优解的选择来达到。每进行一次选择就能得到一个局部的解，把所求问题的解简化成一个规模更小的类似子问题。
-
最优子结构性质
最优子结构是指一个问题的最优解包含其子问题的最优解。
3.2 贪婪法解决部分背包问题
背包问题分为两种情况，一种情况是每个物体都是完整的装入背包即0/1背包问题，另一种情况是物体可以分部分装入背包，本节讨论的正是第二种情况。
假设：xi是物体i被装入背包的部分，0 <= xi <= 1，当xi=0时表示物体i没有被装入背包；当xi=1时表示物体i被全部装入背包。根据问题的要求，可以构造下面的约束方程和目标函数：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}} {{\mat…
于是问题可以归结为寻找一个满足约束方程（1），并使得目标函（2）达到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。
解决方案是：优先选择价值pi最大的物体装入背包，直到最后一个物体装不下时，选择一个适当的物体分割成部分xi<1装入背包。但是采取这种方法不一定能达到最优解，因为如果选择的物体的重量很大，那么背包很快就被装满，使得其他价值高的物体无法继续装入，最终背包的价值并不是最大的。因此，本文所选择的策略都是先计算每个物体的价值重量比，然后将比值大的物体优先装入背包。
3.2.1 算法设计：
首先定义物体的结构体：
typedef struct {
float p; /*物体的价值*/
float w; /*物体的重量*/
float v; /*物体的价值重量比*/
}
贪心算法的核心代码如下：
float knapsack_greedy(float M, OBJECT ob[],float x[], int N) {
float m,p=0;
int n = N;
for (int i = 0; i < n; i++) {
ob[i].v = ob[i].p /ob[i].w;
x[i] = 0;
}
merge_sort(ob, n); /*重新给物体排序，价值重量比大的物体排在前面*/
m = M;
for (int i = 0; i < n; i++) {
if (ob[i].w <= m) {
x[i] = 1;
m -= ob[i].w;
p += ob[i].p;
} else {
x[i] = m/ob[i].w; /*当最后一个物体重量比背包剩余载重量大时，将物体划分成一定比例装入背包*/
p += x[i]*ob[i].p;
break;
}
}
return p;
}
3.2.2 实验结果
输入：物体数量为5，背包载重量为60，背包的价值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理论上输出：背包最大价值159，装入背包的物体为（1，1，1，0.6，0）。
实际输出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jIPC8Ed4-1580817786561)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107114432242.png)]
输入：物体数量为3，背包载重量为50，背包的价值分别是（60，100，120），背包的重量分别是（10，20，30）。
理论上输出：背包最大价值240，装入背包的物体为（1，1，0.67）。
实际输出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Telqk8DO-1580817786561)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200106162748602.png)]
从实验结果可以看出，按照贪婪法的运算步骤可以找到背包问题的最优解。
3.3贪婪算法解决0/1背包问题
假设：xi是物体i被装入背包的部分，xi =0，1，当xi=0时表示物体i没有被装入背包；当xi=1时表示物体i被全部装入背包。根据问题的要求，可以构造下面的约束方程和目标函数：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}}{{\math…
于是问题可以归结为寻找一个满足约束方程（1），并使得目标函（2）达到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。
3.3.1 算法设计
定义数据结构：
typedef struct {
float p; /*物体的价值*/
float w; /*物体的重量*/
float v; /*物体的价值重量比*/
}
输入：背包载重量M，物体的价值p，物体的重量w，物体的个数n。
输出：n个物体被装入背包的分类x[]，背包中物体的总价值。
核心代码如下：
float knapsack_greedy(float M, OBJECT ob[],float x[], int N) {
float m,p=0;
int n = N;
for (int i = 0; i < n; i++) {
ob[i].v = ob[i].p /ob[i].w;
x[i] = 0;
}
merge_sort(ob, n); /*重新给物体排序，价值重量比大的物体排在前面*/
m = M;
for (int i = 0; i < n; i++) {
if (ob[i].w <= m) {
x[i] = 1;
m -= ob[i].w;
p += ob[i].p;
} else { /*当最后一个物体重量大于背包剩余载重量时，不再继续放入物体*/
break;
}
}
return p;
}
3.3.2 实验结果
输入：物体数量为5，背包载重量为60，背包的价值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理论上输出：背包最大价值139，装入背包的物体为（0，1，1，1，0）。
实际输出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k4UweA3j-1580817786563)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107114702514.png)]
输出的129并不是背包能装入的最大价值，如果只装重量为12，20和25的物体，那么背包价值是可达139，比用贪婪法求得的价值要高很多。因此贪心算法不能解决0/1背包问题。
4 动态规划算法
4.1 动态规划的设计思想
动态规划和分治算法类似，其基本思想就是将问题划分为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
动态规划算法的有两个重要的性质：
- 最优子结构性质：即问题的最优解包含子问题的最优解。由每一步的子问题的最优解最终生成问题的最优解。
- 重叠子问题性质：动态规划求解问题时，每次产生的子问题并不总是新的子问题，有些子问题被重复计算多次，这种性质称为重叠子问题。解决方法：将已求得的子问题的解保存起来，避免重复计算相同的子问题。
4.2 动态规划法求解0/1背包问题
假设：xi是物体i被装入背包的部分，xi =0，1，当xi=0时表示物体i没有被装入背包；当xi=1时表示物体i被全部装入背包。根据问题的要求，可以构造下面的约束方程和目标函数：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}}{{\math…
于是问题可以归结为寻找一个满足约束方程（1），并使得目标函（2）达到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。
这个问题也可以用动态规划分阶段决策的方法，来确定把哪个物体装入背包的最优决策。构造下面的动态规划函数：
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {{\mat…
式子（3）表明把前面i个物体装入载重为0 的背包，或者把0个物体装入载重为j的背包，其价值都为0.式子（4）的第一个式子表明：如果第i个物体装入载重量为j的背包，则背包装入前i个物体的总价值和装入前i-1个物体的总价值一样。（4)的第二个式子表明，如果第i个物体的重量小于背包的载重量，则背包装入前i个物体的总价值等于将前i-1个物体装入载重量为（j-wi）的背包所得到的价值量加上物体i的价值pi。如果第i个物体没有装入背包，则背包中的物体价值等于将前i-1个物体装入载重量为j的背包所得的价值。
4.3 算法步骤
设optpn(m)是载重量为m的背包，装入n个物体时得到的最大价值。为了确定装入背包的具体物品，从optpn(m)的值向前倒推，如果optpn(m)大于optp(n-1)(m)，说明第n个物品被装入了背包，则下一步确定把前n-1个物体装入载重量为m-wn的背包中；如果optpn(m)小于等于optp(n-1)(m)，说明第n个物品没有被装入了背包，则下一步确定把前n-1个物体装入载重量为m的背包中。
算法具体步骤如下：
- 初始化，对满足0<=i<=n,0<=j<=m的i和j，令式子（3）成立。
- 令i=1.
- 对满足0<=j<=m的j，按照式子（4）计算optpi(j)。
- i=i+1，若i>n，转步骤5，否则转步骤3。
- 令i=n，j=m。
-
按照
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {\begi…
求第i个分量xi
- i=i-1，若i>0，则转步骤（6），否则算法结束。
4.4 代码实现
//动态规划表
int optp[N][N];
for (int i = 0; i <= n; i++) {
optp[i][0] = 0;
x[i] = 0;
}
for (int j = 0; j <= M; j++) optp[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= M; j++) {
if (j < w[i])
optp[i][j] = optp[i - 1][j];
else {
optp[i][j] = max(optp[i - 1][j], optp[i - 1][j - w[i]] + p[i]);
}
}
}
时间复杂度为O(n*m)
4.5 优化算法
由状态转移方程（4）可知，optp[i] [j]的值仅仅和optp[i] [j-w[i]]和optp[i-1] [j]的值相关，因此可以将上述的二维矩阵优化成为一维矩阵，减少空间复杂度。优化之后，状态转移方程变为optp[i] [j] = max ( optp[i] [j-w[i]], optp[i-1] [j] )。
核心代码如下：
//优化动态规划
int optp[M];
for (int i = 0; i <= M; i++) {
optp[i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = M; j >= w[i]; j--) {
optp[j] = max(optp[j], optp[j - w[i]] + p[i]);
}
}
}
优化之后，算法的时间复杂度和空间复杂度都是O(n*m)，而空间复杂度优化为O(m)。
4.6 实验结果
输入：物体数量为5，背包载重量为10，背包的价值分别是（6，3，5，4，6），背包的重量分别是（2，2，6，5，4）。
理论上输出：背包最大价值15，装入背包的物体为（1，1，0，0，1）。
动态规划的计算步骤表如下：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| 2 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
| 3 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 14 |
| 4 | 6 | 6 | 9 | 9 | 9 | 10 | 11 | 13 | 14 |
| 5 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
实际输出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TDBkw0XN-1580817786564)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200106195740745.png)]
输入：物体数量为5，背包载重量为60，背包的价值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理论上输出：背包最大价值139，装入背包的物体为（0，1，1，1，0）。
实际输出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hglMDrl7-1580817786564)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107115212809.png)]
上述实验证明，动态规划方法可以求解0/1背包问题的最优解。
5 动态规划法和贪婪法对比
共同点：问题具有最优子结构特征，能从子问题的最优解找到原问题的最优解。
不同点：
- 动态规划方法寻找问题最优解时依赖所有子问题的解。而贪心算法从一个局部解开始扩展，作出最优选择后得到一个新的子问题，所作的选择只依赖过去所作的选择，直到找到整体最优解。
- 贪婪法产生的结构图，所作的选择只依赖于过去所作的选择：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RsWF4z6R-1580817786564)(C:\Users\86188\Desktop\贪心算法.png)]
动态规划产生的结构图，它依赖于所有子问题的解：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WbP1qvQk-1580817786565)(C:\Users\86188\Desktop\动态规划.png)]
- 贪心算法的时间复杂度和空间复杂度都是O(n^2)，空间复杂度可以优化为O(n)；动态规划的时间复杂度是O(n*m)，空间复杂度可以优化为O(m)。
- 贪心算法不能求解0/1背包问题，只能求解部分背包问题。而动态规划法既可以求解部分背包问题，也可以求解0/1背包问题。
6 总结
背包问题的三个算法对比，贪婪法只能解决部分背包问题，不能解决0/1背包问题，因为用贪婪法每次装入价值高的物体，背包很快就不能继续装入其他物体，最终的总价值并不是最大的。但是贪婪法在选择背包之前要对物体的价值重量比进行排序，因此贪婪法的时间复杂度是O(n^2)。动态规划法既能解决部分背包问题也能解决0/1背包问题，而且动态规划法在选择物体装入时，不需要对物体的价值重量比进行排序，时间复杂度为O(n*m)。回溯法在求解背包问题上效率并不高。
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)