問題タブ [knapsack-problem]

ここに、ナップザック アルゴリズム (ビン パッキング NP 困難問題) を使用して最適値を計算するコードがあります。

また、パックに含まれる要素を表示する必要があります。選択した要素を配置する配列を作成したい。問題は、この選択をどのステップで実行できるかということです。どのアイテムが取られたかを判断するための他のより効率的な方法はありますか?

最適解の価値だけでなく、最適解を与えてくれるアイテムを知りたい。

ネタバレ：私はhttp://www.spoj.pl/problems/KNAPSACK/に取り組んでいるので、考えられる解決策を台無しにしたくない場合は覗き見しないでください。

ボイラープレート：

ステージを設定するためのいくつかのタイプとヘルパー：

そして主な機能：

そして、このコードは機能します。SPOJサンプルテストケースを接続してみましたが、正しい結果が得られました。しかし、このソリューションをSPOJに送信すると（Luke PalmerのMemoCombinatorsをインポートする代わりに、必要なパーツをコピーして送信されたソースに貼り付けるだけです）、制限時間を超えています。= /

理由がわかりません。0-1ナップザックを実行する効率的な方法について以前に質問しましたが、これはほぼ同じ速さであるとかなり確信しています。メモ化された関数は、生成するために絶対に必要なサブエントリのみを再帰的に計算します。正しい結果。どういうわけかメモ化を台無しにしましたか？このコードに私が見逃している遅い点はありますか？SPOJはHaskellに対して偏見を持っているだけですか？

私も{-# OPTIONS_GHC -O2 #-}提出物の一番上に置きましたが、残念ながら、それは役に立ちませんでした。の2D配列を使用する同様のソリューションを試しましたSequenceが、遅すぎるとして拒否されました。

基本的なプログラミングの原則を独学で学んでいますが、動的プログラミングの問題で行き詰まっています。悪名高いナップザック問題を見てみましょう:

それぞれが重みと値を持つ一連のアイテムを指定して、コレクションに含める各アイテムの数を決定し、合計重量が指定された制限以下になり、合計値ができるだけ大きくなるようにします。

重み制限を 10 に設定し、2 つのリストを与えましょう: weights = [2,4,7] と values = [8,4,9] (これらは作成したばかりです)。制約が与えられた場合に最大値を与えるコードを書くことができますが、それは問題ではありません。しかし、実際に使用した値を知りたい場合はどうでしょうか? 合計値ではなく、個々の値です。したがって、この例では、最大値は重みが 2 と 7 のオブジェクトで、合計値は 8 + 9 = 17 になります。ただし、答えを「17」と読みたくないので、リストの出力が必要です。のように: (8, 9). この問題は簡単かもしれませんが、私が取り組んでいる問題は、はるかに大きく、繰り返し番号を持つリストを使用しています (たとえば、複数のオブジェクトの値は 8 です)。

何か思いつく人がいたら教えてください。いつものように、コミュニティに多くの愛と感謝を。

したがって、標準の多肢選択式ナップサック問題では、各クラスから1つのアイテムを選択して、最適なナップサックを作成できます。ただし、このアルゴリズムを変更して、0個または1個のアイテムを選択できるようにするにはどうすればよいですか？つまり、最適なソリューションを得るために各クラスからアイテムを選択する必要はありませんが、クラスから最大1つのアイテムを選択できます。クラスからアイテムを選択できないのと同じアルゴリズムですか？

ありがとう

私が考えていた、

ナップサック問題のバリエーションを作りたかったのです。

さまざまな重み/値を持つアイテムを使用した元の問題を想像してみてください。

私のバージョンには、通常の重み/値とともに、「グループ」値が含まれます。

例えば。Item1 [5kg、$ 600、電子] Item2 [1kg、$ 50、食品]

さて、このようなアイテムのセットがあるので、ナップサック問題をどのようにコード化して、各「グループ」から最大1つのアイテムが選択されるようにしますか。

ノート：

1. そのグループからアイテムを選択する必要はありません
2. 各グループには複数のアイテムがあります
3. あなたはまだ体重を最小化し、価値を最大化しています
4. グループの数は、それらの値とともに事前定義されています。

この段階でコードのドラフトを作成しているところですが、動的なアプローチを使用することを選択しました。通常のナップサック問題の動的ソリューションの背後にある考え方を理解していますが、これらの「グループ」を組み込むためにこのソリューションを変更するにはどうすればよいですか？

それは私がこれまでに持っているものです、それがこれを解決するたびにそれがいるグループからすべての対応するアイテムを削除するようにそれを追加する必要があります。

これは私の仕事です

ナップザック問題は、コンピューター サイエンスの古典です。最も単純な形式では、ナップザックが指定された総重量になるように、さまざまな重量のアイテムをナップザックに収めようとします。すべての項目に当てはまる必要はありません。たとえば、ナップザックの重量を正確に 20 ポンドにしたいとします。5 つのアイテムがあり、重量は 11、8、7、6、および 5 ポンドです。アイテムの数が少ない場合、人間は検査によってこの問題を解決するのが得意です。したがって、合計が 20 になるのは、8、7、および 5 の項目の組み合わせのみであることがわかります。

このアルゴリズムをどこから書き始めればよいのか、本当にわかりません。階乗と三角形の数に適用される再帰を理解しています。しかし、私は今迷っています。

典型的なLisp方言は、ボトムアップの「動的計画法」アプローチを使用して問題を解決できますか？

（注意：私が理解している限り、Lisp方言を使用して簡単な「メモ化」について話しているのではありません。たとえば、配列を構築するボトムアップの動的計画法について話しているのです。ボトムアップして、導入したばかりの要素を使用して次の要素を計算します。）

たとえば、動的計画法を使用すると、「0-1ナップサック」問題は、他の方法が失敗する入力の疑似多項式時間で解決できます。

必須の（不完全な）解決策は次のとおりです。

さまざまなLisp方言でそのようなことを行うことは可能ですか？いいえの場合、なぜですか？

n重みと値を使用して、通常のアイテムのセット (それぞれ無制限など) を考えると、次のようになります。

と目標重量、総重量が少なくとも、合計値が最小にWなるような項目を選択する必要があります。 W

これは、整数/無制限のナップザック問題のバリエーション (またはある意味ではその逆) のように思えます。DP アルゴリズムの定式化の助けをいただければ幸いです。

解決策を見つけることに成功せずに、与えられたタスクにほぼ 1 週間苦労しているので、このサイトが私の最後の希望です。

値と重量が異なる 20 個のアイテムを持つ0-1 ナップザック問題があり、サックの最大重量は 524 です。総重量が <= 524 で最大値が選ばれたアイテム。

それがどのように機能するかを分析するために、私を指摘するか、詳細な実装を提供してください!! どうもありがとうございました

私は思考の問題に遭遇し、ただイライラしています。私は動的計画法を使用して、ナップザック問題の実用的なアルゴリズムを持っています。

• 最大荷重
• アイテム（重量）

アルゴリズムは、それらのアイテムを使用してナップザックの最適な充填を計算します。しかし、今は最小限のアイテムを使用して完全に埋める必要がありますが、各アイテムの量は無制限です。（これらのアイテムには重量があるため、常に完了することができます）。{1; w1; w2; ...}

これを「クラシック」アルゴリズムにどのように適合させるのですか?

ありがとう