問題. 0-1ナップサック問題(0-1 Knapsack Problem) 個のアイテムからなる集合が与えられる． 番目のアイテムは価値 と重さ を持っている．アイテムをいくつか選び，重み和が 以下で価値の和が最大となるようなものを選べ．

比較可能グラフが理想グラフであることを示します．