现有资金b可用于投资，共有n个项目可供决策者选择.假设j＃项目所需投资额为aj，投资后第二年年初可得利润cj（j＝1，…，n）.又设b，aj，cj均是整数.试问为使第二年年初获得最大利润，决策者应选取哪些项目进行投资？

若令

便得如下整数规划：

上述问题可以解释为一位旅行者在出发前，考虑他的背包内应装哪些物品，使物品重量之和不超过背包允许的负荷，而被装物品的使用价值最大.并因而常称这类问题为0－1背包问题.

下面我们通过对一个具体的0－1背包问题的求解，来说明分支定界法的基本思想.

为讨论方便起见，如果一个问题的可行域为K，今后我们就记该问题为（K）.

例5－18　求解下列0－1背包问题：

其可行域设为K0，该背包问题记为（K0）.

解　若把（K0）的约束条件适当放宽，得到线性规划：

表5－29

图5－7

图5－8(www.daowen.com)

表5－30

图5－9

表5－31

表5－32

图5－10

下面，我们在求解0－1背包问题的基础上，介绍若干分支定界法的术语和记号.这些基本概念对管理中的其他问题建立特定的分支定界法同样也是适用的.

现在我们将讨论的问题转向为：

则称（KS）为一个已被查清的问题.

（7）活问题——若（KS）没有被查清，也没有被划分，则称（KS）为活问题.

（8）剪支——枚举树生长过程中，一旦获得新定界f－，就用它去检查现有活问题，把失去希望的问题改为已被查清的问题.这一过程称为剪支.

（9）分支、父问题和子问题——选择一个活问题（KS）进行划分，称为分支.（KS）称为父问题，KS划分后所得的数个分支问题，称为子问题.