Greedy choice property Optimal substructure To obtain optimal solution for an optimal Optimal substructure: an optimal solution problem, it needs a greedy-choice to a problem contains within it optimal property: A globally optimal solutio on can solutions to the subproblems e arrived at by making a locally optimal (greedy) choice Greedy versus dynamic programmIng 背包问题 Greedy is sufficient ·背包问题:一个包容积有限,每件物体有 Greedy does not work but dynami 不同容积和价值,如何装包使得价值最 programming works 大? Examples ·如果物体不能分割,其最优装包问题叫0 0-1 knapsack problem 1背包问题 Fractional knapsack problem 如果物体可以分割,其最优装包问题叫分 数背包问题 背包问题的贪婪算法 问题实例:包容积50L,3类东西:第 种:60￥、10L、1件;第二种:100￥ 20L、1件;第三种:120￥、30L、1件 贪婪算法 单位容积价格最大的:第一种1件、第二种1 件、第三种23件,价值60+100+80=240￥ 如果0一1背包问题,则贪婪算法只能收获 160￥,而明显的第二种1件+第三种1件可以 装220￥5 Greedy choice property •To obtain optimal solution for an optimal problem, it needs a greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice. Optimal substructure •Optimal substructure: an optimal solution to a problem contains within it optimal solutions to the subproblems Greedy versus dynamic programming •Greedy is sufficient •Greedy does not work but dynamic programming works. •Examples –0-1 knapsack problem –Fractional knapsack problem 清华大学 软件学院 宋斌恒 28 背包问题 •背包问题：一个包容积有限，每件物体有 不同容积和价值，如何装包使得价值最 大？ •如果物体不能分割，其最优装包问题叫0－ 1背包问题 •如果物体可以分割，其最优装包问题叫分 数背包问题 清华大学 软件学院 宋斌恒 29 背包问题的贪婪算法 •问题实例：包容积50L，3类东西：第一 种：60￥、10L、1件；第二种：100￥、 20L、1件；第三种：120￥、30L、1件。 •贪婪算法： –单位容积价格最大的：第一种1件、第二种1 件、第三种2/3件，价值60＋100＋80＝240￥ –如果0－1背包问题，则贪婪算法只能收获 160￥，而明显的第二种1件＋第三种1件可以 装220￥