精确算法求解多维背包问题

摘要

背包问题自提出以来引起学者广泛研究,积累了许多优秀求解算法。精确求解算法主要有动态规划法和分枝限界法,这些算法能精确得到问题的解。虽然精确算法不宜用来直接求解大规模问题,但仍有大量性能优秀的求解背包问题的精确算法。这些算法通常会将问题分割成若干规模不大的子问题,在对子问题用动态规划等精确算法求解,以得到问题较好的解。