用分支限界法求解背包问题（0/1背包）



1.问题描述：已知有N个物品和一个可以容纳TOT重量的背包，每种物品I的重量为Weight，价值为Value。一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总价值最大。



2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示装入，右表示不装入，通过检索问题的解树得出最优解，并用结点上界*不符合要求的结点。-Using branch and bound method to solve knapsack problem (0/1 knapsack) 1. Problem Descr iption: known to have N of items and a TOT can accommodate the weight of backpacks, the weight of each item I for Weight, the value of Value. Add a can or not Add-wide, to solve how to Add items, the backpack can make the total value of the largest items. 2. The design and analysis: the selection of items or not constitute a solution tree, into the left subtree said, indicated that he did not load right, through the solution search tree reached the optimal solution, and the upper bound of node to kill refuses to comply with the requirements of nodes.