最適化
ナップザックの問題
0/1ナップザックを容量DPで厳密に解き、選択品を復元します。一般の最適化問題はNP困難です。
- TIME
- O(nC)（擬多項式時間）
- SPACE
- O(nC)
n = 品物数、C = 整数容量。入力ビット長に対する多項式時間ではない / 上限: 品物0〜200件、0≤容量≤5,000、各重量は0〜5,000の整数、価値は−10⁹〜10⁹の有限数
0/1ナップサック問題を厳密DPで解きます。
最適化
0/1ナップザックを容量DPで厳密に解き、選択品を復元します。一般の最適化問題はNP困難です。
n = 品物数、C = 整数容量。入力ビット長に対する多項式時間ではない / 上限: 品物0〜200件、0≤容量≤5,000、各重量は0〜5,000の整数、価値は−10⁹〜10⁹の有限数
0/1ナップサック問題を厳密DPで解きます。