假设有一个能装入总体积为 T 的背包和 n 件体积分别为 W1,W2,···,Wn 的物品,能否从 n 件物品中挑选若干件恰好装满背包,即使 W1+W2+···+Wn=T,要求找出所有满足上述条件的解。例如:当 T=10,共 6 件物品,物品的体积为{1,2,3,4,5,8},那么可找到下列 4 组解:(1,2,3,4)、(1,4,5)、(2,3,5)、(2、8)。
2 实现提示
可利用回溯法的设计思想来解决背包问题。首先,将物品排成一列,然后顺序选取物品装入背包,假设已选取了前 i 件物品之后背包还没有装满,则继续选取第 i+1 件物品,若该件物品“太大”不能装入,则丢弃而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入背包的那件物品“不合适”,应将它取出“丢弃一边”,继续再从“它之后”的物品中选取,如此重复,直至求得满足条件的解,或者无解。由于回溯求解的规则是“后进先出”,因此要用到栈。
使用栈作为该程序的数据结构,利用栈进行语法检查,以深度优先的搜索方式解空间,实现递归过程和函数的调用,在设计时还使用 C 语言的数组及其循环语言来实现程序。 运用回溯法解题,在搜索解空间树时,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。