@背包问题求解 物品体积vi=0.5n=6 2 top」5->2 3->3 3 4 5 2->4 背包容积T=0 0->1 k=6注意内循环条件 章线和队列 进栈 if(T=0) Stacktraverse(S,w);条件满足输出一组解 栈顶元素出栈 计算机教研宦 第16页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第16页 S 背包问题求解 top 8 2->4 3->3 5 5->2 0->1 背包容积T=0 物品体积w[i] i=0…5 n=6 k=5 进栈 0 1 2 3 4 5 if (T == 0 ) StackTraverse(S,w);条件满足输出一组解 k=6 注意内循环条件 栈顶元素出栈
@背包问题求解 物品体积vi=0.5n=6 2 top,3->3 3 4 5 2->4 背包容积T=2 0->1 k=5 章线和队列 栈不空继续找解(注意外循环条件) 计算机教研宦 第17页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第17页 S 背包问题求解 top 8 2->4 3->3 5 2 0->1 背包容积T=2 物品体积w[i] i=0…5 n=6 k=5 0 1 2 3 4 5 栈不空继续找解(注意外循环条件) k=6
@背包问题求解 物品体积vi=0.5n=6 2 top,3->3 3 4 5 2->4 背包容积T=2 0->1 k=6 章线和队列 T不等于0,不输出栈顶出栈 计算机教研宦 第18页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第18页 S 背包问题求解 top 8 2->4 3->3 5 2 0->1 背包容积T=2 物品体积w[i] i=0…5 n=6 k=6 0 1 2 3 4 5 T不等于0,不输出,栈顶出栈
@背包问题求解 物品体积vi=0.5n=6 2 3 4 5 top. 2->4 背包容积T=5 0->1 k=3 k=4 章线和队列 k=4继续入栈 计算机教研宦 第19页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第19页 S 背包问题求解 top 8 2->4 3 5 2 0->1 背包容积T=5 物品体积w[i] i=0…5 n=6 k=3 0 1 2 3 4 5 k=4继续入栈 k=4
@背包问题求解 物品体积vi=0.5n=6 2 ta top4->5 3 4 5 2->4 背包容积T=0 0->1 k=4—k=5 章线和队列 T=0又找到一组解 栈顶元素出栈 计算机教研宦 第20页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第20页 S 背包问题求解 top 8 2->4 3 4->5 2 0->1 背包容积T=0 物品体积w[i] i=0…5 n=6 k=4 0 1 2 3 4 5 T=0又找到一组解 k=5 栈顶元素出栈