問題タブ [knuth]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - O(n^2) の Knuth の最適二分探索木
O(n^2) 時間で実行できる Knuth の最適な二分探索木を実装しようとしています。O（n ^ 3）で実行されているコードがあります。
M はコストの配列です。P は各ノードの確率です。いくつかのアイデアを以下から得ます:動的プログラミング: Knuth による最適な二分探索木 O(n^2) の改良の理由 . 私の場合、3 番目のループを から に変更しようとしfor (j = i; j <= i + s - 1; j++)ましたfor (j = root[s+1][i]; j <= root[s][i-1]; j++)。しかし、うまくいきません。誰かがこの問題について手がかりを教えてもらえますか?
python - 正確なカバー問題ですが、ソリューション内のサブセットの正確な数に制約があります
私は正確なカバーや同様の問題に比較的慣れていないので、ご容赦ください。典型的な正確なカバーの問題があるとします。セットXとXのサブセットSのコレクションが与えられた場合、 Xを正確にカバーするS * ( S のサブセット)を見つけたいと思います。ただし、ソリューションS * に正確にk 個の要素が含まれるようにします。さらに、1つのソリューションで十分です。
Knuth の Algorithm X は、考えられるすべての解を返すように設計されていることを知っています。Knuth のアルゴリズムを実行して、 k 個の要素を持つソリューションが見つかるまでソリューションを反復する必要がありますか、それとも (私が推測するように) もっと良い方法がありますか? 私はところでPythonを使用しています。
コンテキストとして、Xのサイズは <100 ですが、Sのサイズは 10^6 にすることができます。kは 10 未満で比較的小さい。