计算机算法分析第五章作业.ppt

计算机算法分析 习题课 第五章 3 6 7 8 9 11 12 P122-3 ? 3 0/1 背包问题如果将 5.3 节讨论的背包 问题修改成 ? 极大化 ? 约束条件 ? x i =0 或 1 1in ? 这种背包问题称为 0/1 背包问题它要求物品 或者整件装入背包或者整件不装入求解此问 题的一种贪心策略是按 p i /w i 的非增次序考虑 这些物品只要正被考虑的物品能装的进就将 其装入背包