秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进

 给定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”表示不被