問題タブ [knapsack-problem]

すべて異なるサイズのリンクをたくさん持つのではなく、すべてのタグを同じサイズにしたいと考えています。ただし、私の目標は、クラウドを作成するために必要なスペースの量を最小限に抑えることです。つまり、使用する行数を最小限に抑えることです。

次の例を見てください。

_{(出典: stevethomas.com.au )}

通常のタグ クラウドのように見えます。ただし、「roughdiamond」タグの周りの余分なスペースをすべて見てください。これは、下部近くの「石」などの他のタグで埋められる可能性があり、雲から余分な線全体を効果的に排除できます.

新しい行を開始する前に、単語の上に可能なスペースを埋めるにはどうすればよいですか? 必要な絶対最小行数を見つけるためにそれらを再編成することについて話しているのではありません。画像のリストを調べていた場合、「ペンダント」、「ハウライト」、「イグリス」は 1 行目に移動し、1 行目がいっぱいなので「ラフダイヤモンド」は 2 行目に移動し、「トルマリン」は 2 行目に移動します。 'emberald' と同じように、1 行目または 2 行目に収まらないため 3 行目に移動しますが、'pearl' は余分なスペースがあるため、2 行目に収まるため、2 行目に移動します。おそらく、CSS でこれを行う何らかの方法があり、リンクが収まる入力可能なスペースにリンクを単純に折りたたむ方法があると思います。

ただの好奇心の質問。クラスのグループワークで、教授が人々を特定の数のグループに分割したことを覚えていますか（n）？

私の教授の何人かは、n一緒に働きたい人と一緒に働きたくない人のリストを各学生から取り、次に、学生が好きな人と一致し、一緒に働くことを避ける場所nのグループを魔法のように見つけますn彼らが好まない人々。

私には、このアルゴリズムはナップサック問題によく似ていますが、この種の問題に対するあなたのアプローチについて質問したいと思います。

編集：私の質問とまったく同じようなものを説明しているACMの記事を見つけました。既視感の2番目の段落を読んでください。

最近、マルチナップザック問題の伝統的な遺伝的アルゴリズムを改善しています。したがって、私の改良された遺伝的アルゴリズムは、従来の遺伝的アルゴリズムよりもうまく機能しています。テストしました。(私は OR-Library ( http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html ) から公開されているものを使用して GA をテストしました。) 他の改善された GA を知っている人はいますか? 他の改良された遺伝的アルゴリズムと比較したかったのです。実はネットで調べました。しかし、比較するのに適したアルゴリズムが見つかりませんでした。

ナップザック問題について勉強しています。ですから、ここで1つのことがわかりません。

利益/疑似リソース消費率

U _j = P _j / W _j W _j = R _ji * A _j

皆さんがこの式を知っていることを願っていますので、これ以上の説明は不要だと思います。
ここで Aj を計算したかったのです。そのLP緩和とは。総容量と重量（アイテムのサイズ）を使用して計算する方法。n個のアイテムとm個の容量がある場合、m個のLP緩和変数を持つ必要があることを意味します。そうですか？

のように言う誰か

妥当な乗数を得る最も簡単な方法の 1 つは、変数 x _jが区間 [0, 1] から任意の値を取得できる線形計画法 (LP) 緩和 MKP を解き、双対変数の値を代理乗数。換言すれば、ａ_ｊは、ＬＰ緩和ＭＫＰにおけるｊ番目の制約のシャドープライスに設定される。

LP 緩和 MKP の j 番目の制約のシャドー プライスをどのように計算しているか。しばらくGoogleで検索していますが、あまり明確ではありません。簡単な方法で理解できる人はいますか？

ここまで読んでくれてありがとう:)

この緩和をどのように計算するか。それを見つけるために何を知っておくべきですか。n 個のアイテムと m 個のナップサックがあるとします。そこで、m緩和の数を知りたいと思いました。誰かが少なくとも私にいくつかのアイデアを与えることができますか. しばらく探していました。インターネット上にいくつかの記事がありますが、あまり明確ではありません。少なくとも誰かが私にこのことを読むべきだと言ってください、あなたはこのことを知っておくべきです.

ありがとうございました

配送に必要な箱のサイズを計算するための最良の方法を見つけようとしています。

サイズの異なる3つの輸送コンテナがあります。製品の幅、長さ、深さ、および質量をデータベースで定義しています。

発送に必要な最小の箱の数と、カート内のアイテムの数を考慮したそれらの箱の最小の寸法を見つける方法を知りたいです。

私の現在の「アイデア」は、製品配列全体の最大幅を見つけ、それに応じてボックスを選択し、必要に応じて注文を分割することです...これはうまくいかないようです。

私のボックスのサイズは次のとおりです。-8x6x 6=228立方インチ-10x8 x 8=640立方インチ-12.5x12.5 x 12.5=1953.125立方インチ

製品は次のように定義されます。

ナップサック問題、パッキング問題などを調べましたが、これを行う方法が見つかりません。どんな助けでも素晴らしいでしょう。

私は遺伝的アルゴリズムを使用してナップサック問題に取り組んできました。しかし、私はいくつかの困難に遭遇しました...

まず、ユーザーはテキストドキュメントに保存されるデータセットを生成します。そこからデータをプログラムに読み込みます。

私は、フィットネス値を計算し、親を選択し、子供を産み、そして子供を突然変異させるプログラムをうまく取得しています。しかし、何らかの理由で、人口が少ない場合にのみ機能します。私のプログラムは、人口が少ない場合は一貫して進化しますが、人口が多い場合は非常に一貫性がありません。

例：人口が約10〜200人の場合、遺伝的アルゴリズムは問題なく実行されます。しかし、人口が増えると（約300人以上）、[実行]をクリックしても何も起こりません。次に、プログラムを再起動し、まったく同じデータセットを使用すると、プログラムは正常に実行されます。

コードのどの部分が問題を引き起こしているのかわからないので、サンプルコードが必要な場合は、コードのどの部分（親の選択、データセットの読み込みなど）を教えてください。

どうもありがとう！

ナップサックアルゴリズムを使用してこの問題のアルゴリズムを実装する方法を知っている人はいますか？

現在使用している方法では、LINQとコレクションのコレクションおよびいくつかの辞書を多用しています。私が何について話しているのかわからない人は、板取り問題をチェックしてください。

何かを最適化するのではなく、ナップザックの可能なすべてのパッキング (「不完全な」パッキングを含む) をリストしたいと思います。もちろん、オブジェクトのセットのすべてのサブセットをループして、重みの制約を満たすものを選択することもできます (サブセットのサイズに上限を設定することで改善できます)。効率的。

ありがとう。

私は問題を解決しようとしています（phpでは、プログラミング言語は関係ありません）。お金を払った人がn人いて、n人が支払った金額の合計と同じ金額を支払う人がm人います。これらの人の間の送金の最短ルートを計算したいと思います。支払いを分割して、別の人に支払うことが可能です。理想は、1人が1つまたは2つのトランザクションのみを行うことです。誰かが私を正しい方向に向けたり、これを手伝ってくれるかもしれませんか？

例：Aさんが100ドルを支払った

Bさんは200ドルを支払いました

Cさんは50ドルを支払いました

Dさんは24ドルを支払います

Eさんは175ドルを支払います

Fさんは151ドルを支払います

これに対する1つの可能な解決策は

人物Eは人物Aに100ドルを支払います。

EさんはBさんに75ドルを支払います。

FさんはBさんに125ドルを支払います。

FさんはCさんに26ドルを支払います

DさんはCさんに24ドルを支払います