大きな問題を小さな問題に分けて各個に結論を出していく方法を分割統治法、小問題を、必要性の有無とは無関係にあらかじめ解いておき、必要に応じて活用する方法を動的計画法と言う。動的計画法の代表的なアルゴリズムが、ナップザック問題である。