计算机算法分析与设计 ( 研究生 ) 全册配套课件 ( 二 ) 0-1 背包问题 (0-1Knapsack Problem )设有 n 个物体和一个背包 , 物体 i 的重量为 wi 价值为 pi 背包的载荷为 M,若将物体 i(1 i n,) 装入背包 , 则有价值为 pi .目标是找到一个方案 , 使得能放入背包的物体总价值最高算法设计与分析 > 回溯法若取 W= (20,15, 15), P= (40,25, 25), C=30例 题有限离散问题总可以用穷举法求得问题的全部 .例如 取 N=3 , 问题所有可能的解为 ( 解空间 ): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) 可表示为一棵 3 层的完全正则二叉树时间复杂性 : O(2n)求解过程相当于在树中搜索满足条件...
