归东程子太深 SHANDONG UNIVERSITY OF TECINOLOGY 华容约深完是红器分深是容 假设有面值为1分、5分、1角1分的货 币，需要找给顾客1角5分现金， 仍按贪心算法如何？ 2025年4月3日
2025年4月3日 6 假设有面值为1分、5分、1角1分的货 币，需要找给顾客1角5分现金， 仍按贪心算法如何？
归东程子太军 1.2贪心算法的基本要素 SHANDONG UNIVERSITY OF TECHNOLOGY ●贪心选择性质 ■所谓贪心选择性质是指所求问题的整体最优解可 以通过一系列局部最优的选择，即贪心选择来达 到。 ■对于一个具体问题，要确定它是否具有贪心选择 性质，必须证明每一步所作的贪心选择最终导致 问题的整体最优解。 ●最优子结构性质 ■当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质。 2025年4月3日 7
2025年4月3日 7 1.2 贪心算法的基本要素 ⚫贪心选择性质 ◼所谓贪心选择性质是指所求问题的整体最优解可 以通过一系列局部最优的选择，即贪心选择来达 到。 ◼对于一个具体问题，要确定它是否具有贪心选择 性质，必须证明每一步所作的贪心选择最终导致 问题的整体最优解。 ⚫最优子结构性质 ◼当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质
山东程子太军 13贪心算法正确性证明方法 SHANDONG UNIVERSITY OF TECINOLOGY 会是33☆ ●证明算法所求解的问题具有贪心选择性； ●证明算法所求解的问题具有最优子结构； ●证明算法确实按照贪心选择性进行局部优化选 择。 2025年4月3日
2025年4月3日 8 1.3 贪心算法正确性证明方法 ⚫ 证明算法所求解的问题具有贪心选择性； ⚫ 证明算法所求解的问题具有最优子结构； ⚫ 证明算法确实按照贪心选择性进行局部优化选 择
归东置子太军 14动态规划与贪心算法的比较 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会器空会的会路 ●相同点： ■都具有最优子结构性质。 ●不同，点： ■贪心算法具有贪心选择性质； ■动态规划算法具有子问题重叠性，子问题空间小； ■动态规划算法通常以自底向上的方式解各子问题； ■贪心算法则通常以自顶向下的方式进行，以迭代的方式作出 相继的贪心选择，每作一次贪心选择就将所求问题简化为规 模更小的子问题。 ●可用贪心算法时，动态规划方法可能不适用； ●可用动态规划方法时，贪心算法可能不适用。 2025年4月3日 9
2025年4月3日 9 1.4 动态规划与贪心算法的比较 ⚫ 相同点： ◼ 都具有最优子结构性质。 ⚫ 不同点： ◼ 贪心算法具有贪心选择性质； ◼ 动态规划算法具有子问题重叠性，子问题空间小； ◼ 动态规划算法通常以自底向上的方式解各子问题； ◼ 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出 相继的贪心选择，每作一次贪心选择就将所求问题简化为规 模更小的子问题。 ⚫ 可用贪心算法时，动态规划方法可能不适用； ⚫ 可用动态规划方法时，贪心算法可能不适用
归本程子末军 1.50-1背包问题和背包问题 HANDONG UNIVERSITY OF TECINOLOGY 3会空会点会.3会条 ●0-1背包问题： ■给定n种物品和一个背包。物品的重量是W,价值为 V,背包容量为C。应如何选择装入背包的物品，使 得装入背包中物品的总价值最大？ ■在选择装入背包的物品时，对每种物品只有2种选择， 即装入或不装入。 ●背包问题： ■与0-1背包问题类似，所不同的是在选择物品装入背 包时，可以选择物品的一部分，而不一定要全部装 入背包，1i≤n。 2025年4月3日 10
2025年4月3日 10 1.5 0-1背包问题和背包问题 ⚫ 0-1背包问题： ◼ 给定n种物品和一个背包。物品i的重量是Wi，价值为 Vi，背包容量为C。应如何选择装入背包的物品，使 得装入背包中物品的总价值最大? ◼ 在选择装入背包的物品时，对每种物品i只有2种选择， 即装入或不装入。 ⚫ 背包问题： ◼ 与0-1背包问题类似，所不同的是在选择物品i装入背 包时，可以选择物品i的一部分，而不一定要全部装 入背包，1≤i≤n