問題タブ [knapsack-problem]

実際、私はすでにこの質問に対する部分的な答えを持っていますが、この貪欲なコードの小さな断片を一般化して、最適な解決策に近づけることができるかどうか疑問に思っています.

この問題にどのように遭遇したか（問題自体には関係ありませんが、興味深いかもしれません）：

オブジェクトの大規模なコレクション (堤防のプロファイルのセットであり、各堤防はその長さに沿って多かれ少なかれ同じ形状を維持します) を受け取り、プロパティ (堤防の名前) に従ってそれらをグループ化できます。私のプログラムの出力は、手動で呼び出す必要がある外部プログラムに送られ (理由は聞かないでください)、失敗から回復することはできません (1 つの間違いでバッチ全体が停止します)。

私がこれを使用しているアプリケーションでは、ビンの量やビンの最大サイズに厳しい要件はありません。私がやろうとしていることは

• グループの数を少なく保ちます (プログラムを数回呼び出します)。
• セットを小さく保つ (バッチが失敗した場合のダメージを減らす)
• 似たようなものをまとめる (グループの失敗は、おそらくグループ全体の失敗です)。

あまり時間がなかったので、セットをグループ化する小さな貪欲な関数を書きました。

同僚は、データにノイズを追加して、見つけた近似解の近傍を探索することができると提案しました。

真の最適解を必要としない元のタスクに関連しているわけではありませんが、この質問をコミュニティと共有して、そこからどのようなコメントが出てくるか見てみようと思いました。

無向グラフの色付けに使用する色数を決定する C++ プログラムを作成する必要があります。

また、本「C++疑似コードを使用したアルゴリズムの基礎」のアルゴリズムを使用してこれを行う必要があります。

問題の説明:隣接する頂点が同じ色にならないように、無向グラフの頂点を m 色のみを使用して色付けできるすべての方法を決定します。

入力:正の整数 n と m、および n 個の頂点を含む無向グラフ。グラフは 2 次元配列 W で表され、行と列の両方に 1 から n までのインデックスが付けられます。ここで、i 番目の頂点と j 番目の頂点の間にエッジがある場合は W [i] [j] が true であり、そうでない場合は false です。 .

出力: 2 つの隣接する頂点が同じ色にならないように、最大​​で m 色を使用する、グラフのすべての可能な色付け。各カラーリングの出力は、1 から n までのインデックスが付けられた配列 vcolor です。ここで、vcolor [i] は i 番目の頂点に割り当てられた色 (1 から m までの整数) です。

そこにアルゴリズムがあります：

そして最後にコメントしてください:通常の規則に従って、n、m、W、および vcolor はどちらのルーチンにも入力されません。アルゴリズムの実装では、ルーチンは、n、m、および W を入力として持つ単純な手順でローカルに定義され、vcolor はローカルで定義されます。m_coloring の最上位呼び出しはm_coloring( 0 ) です。

私は自分自身の実装を書き始めます。最初に言いたいのは、私は C++ プログラマーが得意ではないということです。さらに、普段は JS や PHP などの弱い型付け言語を使用しているので、もっとうまくできることがたくさんあると確信しています。しかし、それは主な問題ではありません。

問題は:上記のプログラムが動作し始め、簡単なグラフを書きます:

4 つの頂点、4 つのエッジ

1 2
1 3 2 3 3 4

次に、プログラムはcheckFor()を使用し始めます(次の色数ごとに for() で使用する予定でしたが、テスト目的で静的に使用するため、4 を使用しました。

残念ながら、プログラムは m_coloring() を起動し、次に promise() を起動し、そして...これで終わりです。私は最後の 3 時間を費やして、自分が何を間違っているかを調べました。経験豊富なプログラマーなら、私が何をすべきか、および/または何が間違っているかを説明できるかもしれません...

助けてください、どうもありがとう。

私のプログラムコード:

ナップザック問題を動的計画法で解きたい！アイテムはナップザックに入れるべきかどうか、同じアイテムを何度もナップザックに入れたくありません!

このコードを見てきましたが、これを使用すると、同じオブジェクトを複数回追加できます

次に、オブジェクトがナップザックにあるかどうかを確認するために配列を作成しようとしましたが、このプログラムは正常に機能しませんでした!

皆さん、私を助けてくれませんか? :)

材料の落下や無駄を最小限に抑えてネスティングしようとしています。

私はグリーディ アルゴリズム、ビン パッキング、ナップザック、1D-CSP、ブランチ アンド バウンド、ブルート フォースなどを調べました。私はそれがカッティングストックの問題であると確信しています。これを実行するための関数を考え出すのに助けが必要です。ストックの長さは 1 つだけではなく複数あり、ユーザーはあまり一般的ではない長さの在庫を入力する場合があります。PHP で使用する関数またはアルゴリズムを考え出して、最適化された切断パターンと無駄を最小限に抑えて必要なストックの長さを考え出す際の助けをいただければ幸いです。

ありがとう

次のような問題があります。

1. さまざまな機能 (整数) を持つオフィスの場所とリソースはほとんどありません。
2. すべてのリソースをさまざまなオフィスの場所に分散して、すべてのオフィスの場所の機能が可能な限りバランスがとれるように、それらを場所間でほぼ均等に分割する最善の方法を見つけたいと考えています。注意すべき点がいくつかあります。

• 各オフィス ロケーションのリソース数の差は 1 を超えてはなりません。• 各オフィス ロケーションの機能 (個々の機能を追加することによって達成される) は、互いに可能な限りほぼ等しくする必要があります。

インターネットで調べたところ、この問題に近いと思われる Knapsack アルゴリズムと Bin-pack アルゴリズムについて知りました。

例: オフィスの場所の数 = 3; 人数 = 8; 人の能力 = 10、20、5、150、90、200、250、140 (8 つのリソースの能力値);

上記の数値はサンプルです。リソースとそれぞれの機能の値が 1000 以上になる可能性があります。オフィスの場所の数も変更できます。

正しいパスをたどる自信がない限り、プログラミングの部分を開始しませんでした。これを解決するための正しい方向に私を導くためにあなたの助けを求めています.

また、これの可能性のある疑似コードを共有できれば、非常に役立ちます。

ありがとう！

より大きなリストからアクティビティのサブセットを選択するアルゴリズムを開発しようとしています。選択した場合、各アクティビティは一定量の固定リソースを使用します (つまり、選択したアクティビティの合計が総予算を下回っている必要があります)。複数の実行可能なサブセットが存在する可能性があり、それらから選択する手段は、選択されていない活動の機会費用の計算に基づいています。

編集:これが0-1 ナップザックの問題ではない理由が 2 つあります。

• ナップサックでは、重み (つまり、消費されるリソース) に整数値が必要ですが、私のリソース消費 (つまり、ナップザックの用語では質量) は連続変数です。(明らかに、ある程度の精度を選択して必要なリソースを量子化することは可能ですが、ビンのサイズは非常に小さくする必要があり、ナップサックはO(2^n)W.
• アプリオリに機会費用を計算することはできません。つまり、それぞれの活動の適合性を個別に評価することはできませんが、特定の一連の選択された活動の効用や、既存のリストに追加のタスクを追加することによる限界効用を評価することはできます。

私が行った調査では、素朴なアプローチが示唆されています。

パワーセットを定義するパワーセット
の各要素について、セットにない項目に基づいてその効用を計算します
最高の効用を持つ要素を選択します

ただし、実行時間と必要なメモリを高速化する方法があることは知っています。例えば：

• パワーセットを完全に列挙するO(2^n)ことはできますが、リストを完全に列挙する必要はありません。予算を超えるタスクのセットを見つけたら、それ以上のタスクを追加するセットは実行不可能であり、拒否される可能性があることがわかっているからです。つまり、{1,2,3,4}が実行不可能な場合、 も実行可能です{1,2,3,4} U {n}。ここで、n は、より大きなリストに残っているタスクのいずれかです。
• 私は義務を要約しているだけなので、タスクの順序は重要ではありません (つまり、実行可能であれば、 、 など{1,2,3}もそうです)。{2,1,3}{3,2,1}
• 最終的に必要なのは選択されたセットだけなので、おそらく比較目的でこれまでに見つかった最高の効用値のみが必要です。
• すべての実行可能なものを確認したと確信できる限り、リストの列挙を保持する必要はありません。（ただし、以前に計算された実行可能なサブセットのデューティ合計を維持すると、実行時間が短縮される可能性があると思います。）

優れた再帰アルゴリズムが機能すると確信していますが、疑似コードであっても、それを定義する方法がわかりません (おそらく、いくつかの言語で実装されるため、これが最も理にかなっています-おそらくプロトタイピング用の Matlab と、後でコンパイルされた言語)。

0から3までの値の5x5テーブルがあり、すべての値が不明です。各行と列の値の合計とゼロの数の両方を知っています。C＃を使用してこの0-1ナップサック問題を解決し、既知の合計とゼロの数を満たす可能な解決策を取得するにはどうすればよいですか？テーブルは常に5行5列になるため、従来のナップザックではありません。

たとえば、次のように入力するとします。

私たちはこれを可能な解決策として得るでしょう：

このかなり奇妙な状況では、どのタイプのアルゴリズムを採用する必要がありますか？順列を列挙するためだけにクラスを作成する必要もありますか？

明確にするために編集します。問題は、可能性を列挙できないことではありません。指定された数のゼロと最大5つの項目を含みながら、任意の合計に追加する順列を効率的に決定する方法がわからないということです。

次の問題:

曲を含むMySQLデータベースがあります。データベースの構造は次のとおりです。

ユーザーは特定の時間を php フォームに入力できる必要があり、php 関数は指定された時間 ±X 分になる曲のすべての可能な組み合わせのリストをユーザーに提供する必要があります。

したがって、ユーザーが 1 時間±5 分の音楽を聴きたい場合、フォームに 60 分と 5 分のしきい値を入力し、合計で 55 ～ 65 分になるすべての可能な曲セットを受け取ります。重複を出力するべきではありません。

私はすでにこの問題へのいくつかのアプローチを見つけましたが、それらは曲名などではなく、Xになるまでの期間のみを返しました。したがって、私の問題は、これを解決して追加する曲のIDを返す方法ですするか、対応する曲名のリストを印刷します。

これは私が見つけた最良の答えの 1 つに思えますが、データベースに適応させることができません。

これは、オフィス ホッケー プールで優勝するチャンスを最大限にしようと始めた、ちょっとした楽しいプロジェクトです。最高サラリーキャップ内で最も多くのポイントを獲得できる 20 人の選手を選ぶ最善の方法を見つけようとしています。

たとえば、生データが

1. プレイヤー名
2. ポジション（フォワード、ディフェンス、ゴールキーパー）
3. 今シーズンの予想ポイント数
4. 給料。

X サラリー キャップ内で最も多くのポイントを獲得できる 20 人のプレーヤーが必要です。後で、フェーズ 2 として同じことをしたいと思いますが、この場合、12 人のフォワード、6 人のディフェンス、2 人のゴールキーパーだけが必要です。

明らかな方法は、考えられるすべての組み合わせを単純に実行することですが、これは機能しますが、500 人のプレイヤーの場合のように有効なオプションではありません。考えられる組み合わせが多すぎます。いくつかのスマート フィルターを追加して、500 人のプレーヤーを上位 50 人のフォワード、上位 30 人のディフェンス、上位 15 人のゴールキーパーに減らすこともできますが、それでも、これは非常に遅いプロセスになります。

これを実装する他のアルゴリズムがあるかどうか疑問に思っています。これは単なる遊びであり、重要なビジネス リクエストではありません。しかし、今後の進め方についてご意見がございましたら、お気軽にお問い合わせください。

私の最初の試みは、他の情報源からの助けを借りて、ナップザック アルゴリズムを使用することでした。パラメータとして給与だけで動作するようです。20 プレイヤーのチーム パラメータを追加する方法を理解するのに苦労しています。.Net ですが、Java に簡単に変換できるはずです。

別のループを実行して、給与に関係なく 20 人のプレーヤーで最高のチームを見つけ出し、2 つのリストで最も高いチームが見つかるまで 2 つのリストを比較することを考えていました。わからない。

ご協力いただきありがとうございます！