@递归调用执行情况如下: 0 print(0); 主程序 prin(1)(4)输出:1 返回 print(2); (3)输出:2,2 w=3 运行结果 print(w) (2)输出:3,3,3 结束 P top top (3)1 top 2)2 2)2 (2)2 一(1)3[(u)3[(1)3[()3 计算机教研室 第11页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第11页 递归调用执行情况如下： 主程序 (1) print(w) w=3; 3 print(2); （1）w=3 top (2) 输出：3, 3, 3 w 2 print(1) ; （2）w=2 （1）w=3 top (3) 输出：2, 2 w 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1 w 0 （4）w=0 （3）w=1 （2）w=2 （1）w=3 top w (3) 输出：2, 2 (2) 2 (1) 3 top (4)输出：1 (3) 1 (2) 2 (1) 3 top (2) 输出：3, 3, 3 (1 ) 3 top 返回 (3) 1 (2) 2 (1) 3 top (4) 0 结束 (1) 运行结果： 1， 2，2， 3，3，3
@背包问题求解 物品体积vi=0.5n=6 4 2 3 4 5 背包容积T=10 k=0 章线和队列 top 计算机教研宦 第12页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第12页 背包问题求解 top 8 4 3 5 2 S 1 背包容积T=10 物品体积w[i] i=0…5 n=6 k=0 0 1 2 3 4 5 k
@背包问题求解 物品体积vi=0.5n=6 4 2 3 4 top. 1->8 背包容积T=1 0->1 K=0,1进栈k=3,4,5放不进去k=6 章线和队列 注意内循环条件 while(T>0&&k<n) k=1(体积8必须出栈 计算机教研宦 第13页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第13页 S 背包问题求解 top 1->8 4 3 5 2 0->1 背包容积T=1 物品体积w[i] i=0…5 n=6 k=2 放不进去 0 1 2 3 4 5 K=0,1k=3 进栈k=4 ,k=3,4,5 放不进去 ,k=6 注意内循环条件while (T >0 && k < n ) k=1(体积8)必须出栈
@背包问题求解 物品体积vi=0.5n=6 4 2 3 4 5 背包容积T=9 top.0-> k=2,3进栈 章线和队列 外循环条件 while(( Stack Empty(S)&&k=n) 计算机教研宦 第14页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第14页 S 背包问题求解 top 8 4 3 5 2 0->1 背包容积T=9 物品体积w[i] i=0…5 n=6 k=1 0 1 2 3 4 5 k=2,3进栈 外循环条件while (!(StackEmpty(S) && k == n));
@背包问题求解 物品体积vi=0.5n=6 2 top」3->3 3 4 2->4 背包容积T=2 0->1 2,3进栈k=4放不下一k=5 章线和队列 计算机教研宦 第15页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第15页 S 背包问题求解 top 8 2->4 3->3 5 2 0->1 背包容积T=2 物品体积w[i] i=0…5 n=6 2,3进栈 k=4 放不下 0 1 2 3 4 5 k=5