1つのバッグ（容量：2V）または2つのバッグ（各容量：V）の0/1古典的なkanpsackでは、どちらが良いでしょうか？

Question

これは古典的な0/1のナップザック問題の変形だと思います。 つまり、与えられた容量制限（Say 2V）でいくつかの宝を盗むことを計画していると仮定します。しかし、指定された容量制限では、2つの選択肢があります：容量2Vの1つのバッグ、または容量がVの2つのバッグ。どのソリューションがより良いかを事前に計算するために使用できる数式がありますか（最適な価値を提供します）？あるいは、異なる再発規制によって最適値を別々に計算し、より良い値を選択する必要がありますか？

これ以上一般的には、容量制限（V）がある場合、capcity Vで1袋、capcity V/kでk袋を取って盗むことができます。そして問題を解決するために最高のものを選択してください。

Answer 1

1つのバッグは常に良いです。 nバッグ溶液の内容物は、常に1つのバッグに収めることができるが、その逆は不可能である。