根据题意,从n个物品中选择一些物品,相当于从n个物品组成的集合S中找到一个子集,这个子集内所有物品的总重量不超过购物车容量,并且这些物品的总价值最大。S的所有的子集都是问题的可能解,这些可能解组成了解空间,我们在解空间中找总重量不超过购物车容量且价值最大的物品集作为最优解。
这些由问题的子集组成的解空间,其解空间树称为 子集树 。