容量5kgのナップサックに、次の4つの品物から選んで詰める。品物は分割できない。A：重さ2kg・価値30、B：重さ3kg・価値40、C：重さ4kg・価値50、D：重さ1kg・価値15。詰めた品物の価値の合計の最大値はいくらか。

解説

正解は「70」です。0-1ナップサック問題では、各品物を入れるか入れないかの組合せの中から、重さの合計が5kg以下で価値が最大のものを求めます。5kg以内の主な組合せは、A と B（5kg・70）、C と D（5kg・65）、B と D（4kg・55）、A と D（3kg・45）などで、最大は A と B の70です。「65」は、最も価値の高い C を優先して選び、残りに D を入れた場合です。「55」は B と D の組合せです。「45」は、重さあたりの価値が高い順（D、A、B、C）に入る限り詰める貪欲法の結果です。D と A を入れると次の B が入らないため、0-1ナップサックでは最適になりません。