数据结构 背包问题.docx

{ { { { 背包问题的求解 问题描述 假设有一个能装入总体积为T的背包和n件体积分别为W1,W2,wn的物品 能否从n件物品中挑选若干件恰好装满背包即使 W1+W2++Wm=T,要求找出 所有满足上述条件的解 例如当T=10,各件物品的体积1,8,4,3,5,2时可找到下列4组解 () (1,4,5) (8.2) 实现提示 可利用回溯法的设计思想来解决背包问题 首先将物品排成一列