给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为W。一种物品要么全部装入背包,要么全部不装入背包,不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品,使得装入背包中的物品总价值最大?
01、问题分析——解空间及搜索条件
根据问题描述可知,0-1背包问题要求找出n种物品集合{1,2,…,n}中的一部分物品,将这部分物品装入背包。装进去的物品总重量不超过背包的容量且价值之和最大,即找到n种物品集合{1,2,…,n}的一个子集,这个子集中的物品总重量不超过背包的容量,且总价值是集合{1,2,…,n}的所有不超过背包容量的子集中物品总价值最大的。
按照回溯法的算法框架,首先需要定义问题的解空间,然后确定解空间的组织结构,最后进行搜索。搜索前要解决两个关键问题,一是确定问题是否需要约束条件(用于判断是否有可能产生可行解),如果需要,那么应如何设置?二是确定问题是否需要限界条件(用于判断是否有可能产生最优解),如果需要,那么应如何设置?
1●定义问题的解空间
0-1背包问题是要将物品装入背包,并且物品有且只有两种状态。第i(i=1,2,…,n)种物品是装入背包能够达到目标要求,还是不装入背包能够达到目标要求呢?很显然,目前还不确定。因此,可以用变量xi表示第i种物品是否被装入背包的行为,如果用“0”表示不被