algorithm - 多肢選択式ナップザック

Question

したがって、標準の多肢選択式ナップサック問題では、各クラスから1つのアイテムを選択して、最適なナップサックを作成できます。ただし、このアルゴリズムを変更して、0個または1個のアイテムを選択できるようにするにはどうすればよいですか？つまり、最適なソリューションを得るために各クラスからアイテムを選択する必要はありませんが、クラスから最大1つのアイテムを選択できます。クラスからアイテムを選択できないのと同じアルゴリズムですか？

ありがとう

Answer 1

各クラスにゼロ利益/ゼロウェイトの選択肢を1つ追加して、元の問題セットを変更するだけです。