0-1背包问题(0-1Knapsack Problem )
设有n个物体和一个背包,物体i的重量为w
i
价值为p
i
背包的载荷为M,
若将物体i(1i n,)装入背包,则有价值为p
i
.
目标是找到一个方案,使得能放入背包的物体总价值最高
算法设计与分析 >回溯法
若取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(2
n
)
求解过程相当于在树中搜索
满足条件的叶结点.
