そこで、解決したい興味深い問題に出会いました。非決定的な遷移を伴うゲームを解決しようとしていたときに遭遇しました。この問題について聞いたことがある場合、またはそれについて書かれた名前/論文があるかどうかを知っている場合は、私に知らせてください! ここにあります。
n 個のボックスと m 個の要素があり、n1 には i1 個の要素があり、n2 には i2 個の要素がある、など (つまり、i1 + i2 + ... + in = m)。各要素には重み w と値 v があります。値が最大になり、重み <= k (何らかの入力パラメーター) となるように、各 n ボックス (ソリューション サイズ = n) から正確に 1 つの要素の選択を見つけます。
最初に気付いたのは、ソリューションに i1*i2...* があることです。これは 2^m 未満の m を選択します。これは、問題が P にあることを意味しますか (私の数学は少しあいまいで申し訳ありません)。すべてのソリューションを反復処理する必要のないアルゴリズムのアイデアを知っている人はいますか? 近似値は問題ありません。
編集: さて、この問題は実際にはナップザックの問題と同じであるため、NP 困難です。ボックスにそれぞれ 2 つの要素があり、1 つはサイズが 0 で値が 0 で、もう 1 つはサイズが 0 で値が 0 以外の要素であるとします。これはナップザックと同じです。巧妙な疑似多項式時間アルゴリズム/ナップザックへの変換を考えられる人はいますか?