Dynamic Programming - Kapsack Problem (YouTube)を見ました。ただし、制約が予算、価格であり、整数ではなく倍精度であるという、わずかに異なる問題を解決しています。それで、どうすればそれを変更できるのだろうか？Double は、1,2,3 を持つことができる整数とは異なり、「連続的」です .... 0.0、0.1、0.2 を行うとは思いません ...?
更新 1
100 を掛けて double を int に変換することを考えました。お金は小数点以下 2 桁しかありません。しかし、それは値の範囲が非常に大きくなることを意味しますか?
更新 2
私が解決する必要がある問題は次のとおりです。
アイテムには、価格 (倍精度) と満足度 (整数) の値があります。制約として予算があり、満足度を最大化する必要があります。
YouTube 動画では、作者は int[numItems][possibleCapacity(weight)] のような 2 つの 2 次元配列を作成しました。ここでは、予算が整数ではなく倍精度であるため、できません
任意精度の浮動小数点数を使用する場合（つまり、小数点以下の桁数が固定されていない場合）、これらが分数ではない場合、動的計画法は機能しません。
動的計画法の基本は、特定の入力の計算の以前の結果を保存することです。したがって、任意の精度で浮動小数点数を使用した場合、可能な浮動小数点数ごとに実質的に無限のメモリが必要になります。もちろん、無限の計算を行うことは不可能であり、最適ではありません。
ただし、これらの数値の精度が固定されている場合（10進数が2つしかないお金の場合のように）、（前述のように）乗算して整数に変換し、通常どおりナップサック問題を解くことができます。
UPDATE 1 で述べたことを実行する必要があります: 予算とアイテムの価格をセントで表現します (ドルについて話していると仮定します)。次に、任意の精度や連続数について話しているわけではありません。すべての価格 (および予算) は整数になります。その整数がセントを表すだけです。
簡単にするために、予算を 10 ドルと仮定します。問題は、ナップザック容量が次のすべての値を取得する必要があることです。
[0.00, 0.01, 0.02, 0.03, ..., 9.99, 10.00]
値は 2 多です。SOLUTION MATRIX と KEEP MATRIX の各行には 1001 の列があるため、手動で問題を解決することはできません(予算が数百万ドルの場合、コンピューターでさえ苦労する可能性があります)。元の問題（それについては何もできません）。
あなたの最善の策は、KNAPSACK に関する既存のコードを使用するか、独自のコードを作成することです (私はそれをお勧めしません)。
KNAPSACK に関する既存のコードが見つからず、Linux/Mac に精通している場合は、GNU 線形プログラミング キット(GLPK) をインストールして、問題を整数線形プログラムまたはバイナリ線形プログラムとして表現することをお勧めします ( 0-1 ナップザックを解決します)。それはあなたのために問題を解決します (さらに、必要に応じて C、C++、Python、そしておそらく Java を介して使用できます)。GLPK の使用方法については、このすばらしい記事を参照してください (おそらく、整数変数について説明しているパート 2が必要になるでしょう)。GLPK についてさらにヘルプが必要な場合は、コメントを残してください。
編集：
基本的に、私が言おうとしているのは、あなたの制約は連続的ではなく、離散的(セント) であるということです。あなたの問題は、予算が多すぎる可能性があるため、手動で解決できないことです。
予算が数ドルから数百セントになる可能性があるため、怖がらないでください。予算がわずか 18 セントの場合、問題のサイズは YouTube ビデオのものに匹敵します。ビデオの男性は、ナップザックのサイズが 1800 (または 180) の場合、(手で) 問題を解決することはできません。
これはあなたの質問に対する答えではありませんが、あなたが探しているものかもしれません:
Microsoft の Solver Foundation 3を使用して、あなたが説明した問題を解決する簡単なコードを作成しました。ナップザック アルゴリズムではなく、シンプレックス方式を使用します。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.SolverFoundation.Common;
using Microsoft.SolverFoundation.Services;
namespace LPOptimizer
{
class Item
{
public String ItemName { get; set; }
public double Price { get; set; }
public double Satisfaction { get; set; }
static void Main(string[] args)
{
//Our data, budget and items with respective satisfaction and price values
double budget = 100.00;
List<Item> items = new List<Item>()
{
new Item(){
ItemName="Product_1",
Price=20.1,
Satisfaction=2.01
},
new Item(){
ItemName="Product_2",
Price=1.4,
Satisfaction=0.14
},
new Item(){
ItemName="Product_3",
Price=22.1,
Satisfaction=2.21
}
};
//variables for solving the problem.
SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();
Term goal = 0;
Term constraint = 0;
foreach (Item i in items)
{
Decision decision = new Decision(Domain.IntegerNonnegative, i.ItemName);
model.AddDecision(decision); //each item is a decision - should the algorithm increase this item or not?
goal += i.Satisfaction * decision; //decision will contain quantity.
constraint += i.Price * decision;
}
constraint = constraint <= budget; //this now says: "item_1_price * item_1_quantity + ... + item_n_price * item_n_quantity <= budget";
model.AddConstraints("Budget", constraint);
model.AddGoals("Satisfaction", GoalKind.Maximize, goal); //goal says: "Maximize: item_1_satisfaction * item_1_quantity + ... + item_n_satisfaction * item_n_quantity"
Solution solution = context.Solve(new SimplexDirective());
Report report = solution.GetReport();
Console.Write("{0}", report);
Console.ReadLine();
}
}
}
これは、予算制約 (double) を使用して、価格 (double) を持つアイテム数 (integer) の最適な最大値を見つけます。
コードから、いくつかのアイテムの数量を実際の値 (double) で持つことができることは明らかです。これはおそらく、範囲の広いナップザックよりも高速になります (前述の *100 を使用することにした場合)。
追加の制約 (特定のアイテムの数など) を簡単に指定できます。上記のコードは、制約を簡単に定義する方法を示すこの MSDN How-toから改作されています。
あなたは C# を使っていないのではないかと思いました。この場合、多くの言語で線形計画法用のライブラリが多数あり、それらはすべて比較的簡単に使用できると思います。制約と目標を指定します。
あなたのUpdate 2に従って、このコードを更新して満足のいくものにしました。
これを見てください。申し訳ありませんが、私にはコメント権限がありません。
編集 1
制約はナップザックの重量ではなく予算だと言っていますか? これは依然としてナップザックの問題です。
それとも、 Item Values as Integers (0-1 ナップザックの問題) の代わりに、分数があると言っていますか。次に、貪欲なアプローチでうまくいくはずです。
編集 2
あなたの問題を正しく理解していれば..それは述べています
アイテムnの種類は 1 から n まであります。各種類のアイテムiには、値viと価格がありpiます。通常、すべての値と価格は非負であると仮定します。予算はBです。
この問題の最も一般的な定式化は、各種類のアイテムのコピー0-1 knapsack problem数を 0 または 1 に制限するです。xi数学的には、0-1 ナップザック問題は次のように定式化できます。
n
maximize E(vi.xi)
i=i
n
subject to E(pi.xi) <= B, xi is a subset of {0,1}
i=1
ネオ・アドニスの答えはここにあります.動的プログラミングは、実際には任意の精度では機能しません。
しかし、精度を小数点以下 2 桁に制限したい場合は、ビデオで説明されているように続けてください。テーブルは次のようになります。
+------+--------+--------+--------+--------+--------+--------+
| Vi,Pi| 0.00 | 0.01 | 0.02 | 0.03 | 0.04 ... B |
+------+--------+--------+--------+--------+--------+--------+
|4,0.23| | | | | | |
|2,2.93| | | | | | |
|7,9.11| | | | | | |
| ... | | | | | | |
| Vn,Pn| | | | | | answer |
+------+--------+--------+--------+--------+--------+--------+
あなたが言及したように、実数をintに変換することさえできます。
はい、値の範囲は非常に大きく、knapsack is も理解する必要がありますNP-complete。つまり、これを解決するための効率的なアルゴリズムはありません。pseudo polynomialDPを使用した唯一のソリューション。これとこれを参照してください。
答えは完全に正しくありません。
ナップザック問題を整数満足度とダブルスのような任意の実数賞で解く動的プログラムを実装できます。
最初に、整数賞に関する問題の標準的な解決策:
Define K[0..M, 0..n] where K[j, i] = optimal value of items in knapsack of size j, using only items 1, ..., i
for j = 0 to M do K[j,0] = 0
for i = 1 to n do
for j = 0 to M do
//Default case: Do not take item i
K[j,1] = K[j, i-1]
if j >= w_i and v_i+K[j-w, i-1] > K[j, i] then
//Take item i
K[j,i] = v_i + K[j-w_i, i-1]
これにより、エントリ K[M, n] の再帰に従って解を見つけることができるテーブルが作成されます。
実数の重みに関する問題の解決策は次のとおりです。
Define L[0..S, 0..N] where L[j, i] = minimal weight of items in knapsack of total value >= j, using only items 1, ..., i
and S = total value of all items
for j = 0 to S do L[j, 0] = 0
for i = 0 to n do
for j = 0 to S do
//Default case: Do not take item i
L[j,i] = L[j, i-1]
if j >= v_i and L[j-v_i, i-1] + w_i < L[j, i] then
//Take item i
L[j, i] = L[j -v_i, i-1] + w_i
ソリューションは、他のバージョンと同様に見つけることができます。最初の次元として重量を使用する代わりに、最小の重量につながるアイテムの合計値を使用するようになりました。コードの実行時間はほぼ同じ O(S * N) ですが、もう一方のコードは O(M * N) です。
最近 sci.op-research に投稿された質問は、私が考えたくない、あなたが聞いたくない退屈な仕事からの歓迎の休息を提供してくれました。貪欲なヒューリスティックは、連続ナップザック問題 maximumc′xs.ta′x≤bx≤ux∈ℜ+n(1) を最適に解くことがわかっています。(双対性理論を使用した証明は非常に簡単です。) 最大化c′xs.ta′x≤be′x=b˜x≤ux∈ℜ+n(2 ) ここで e=(1,…,1) . 貪欲ヒューリスティックの変種など、シンプレックス法以外で解決できますか?
答えはイエスですが、私が思いついたものがシンプレックス法よりもプログラムが簡単で効率的であるかどうかはまったくわかりません。個人的には、線形計画法のソルバーでライブラリにリンクして、シンプレックスを使用しますが、代替案がシンプレックスの改善ではない場合でも、代替案を見つけるのは面白かったです。
私が提示する方法は、双対性に依存しています。具体的には、線形プログラムの実行可能解とその双対の実行可能解が相補的な緩み条件を満たしている場合、両方がそれぞれの問題で最適であるというよく知られた結果に依存しています。ナップザックとカウント制約の双対変数をそれぞれ λ と μ とします。λ≥0 であるが、μ の符号は無制限であることに注意してください。基本的に、以下で説明する同じ方法は、不等式のカウント制約 (e'x≤b~ ) を使用して機能し、μ (非負) の符号がアプリオリにわかっているため、実際には少し簡単です。元の質問の投稿者は等価カウント制約を指定していたので、それを使用します。上限には双対変数 (ρ≥0 ) もあります。双対問題は最小化されますbλ+b˜μ+u′ρs.t.λa+μe+ρ≥cλ,ρ≥0.(3)
これは論文ではなくブログ投稿であるため、(2) が実現可能であり、すべてのパラメーターが厳密に正であり、最適解が一意で縮退していないと仮定します。一意性と縮退によってアルゴリズムが無効になることはありませんが、プレゼンテーションが複雑になります。(2) の最適な基本実行可能解では、1 つまたは 2 つの基本変数 (ナップザック制約が非拘束の場合は 1 つ、拘束の場合は 2 つ) が存在し、他のすべての変数はその下限または上限のいずれかで非基本的です。(λ,μ,ρ) が (2) の双対の最適解であるとします。任意の変数 xi の削減コストは ri=ci−λai−μ です。ナップザック制約が束縛されていない場合、λ=0 であり、最適解は xi=uiri>0b~-∑rj>0ujri=00ri<0.(4) ナップザック制約が束縛されている場合、2 つの項目 (j , k ) 変数が基本で、 rj=rk=0 。(縮退を想定することで、knapsack 制約の slack 変数が値 0 の基本的である可能性を想定しました)。xi=uiri>00ri<0(5) と設定し、b'=b−∑i∉{j,k}aixi および b~'=b~−∑i∉{j,k}xi とする。2 つの基本変数は、xj=b'−akb˜'aj−akxk=b'−ajb˜'ak−aj で与えられます。(6)
アルゴリズムは 2 段階で処理されます。まず、ナップザックの非バインド (1 つの基本的な x 変数) を使用して解を探し、次にナップザックのバインド (2 つの基本的な x 変数) を使用して解を探します。相補的な緩みに従う実行可能な主解と双対解を初めて見つけたとき、両方が最適でなければならないことに注意してください。また、任意の μ と任意の λ≥0 が与えられた場合、ρi=ci−λai−μ+ を設定することにより、(3) の実行可能な解を得ることができます。したがって、実行可能な双対解を常に扱い、アルゴリズムは相補的な緩みを満たす主解を構築します。したがって、停止基準は、構築された主解が実行可能であるということになります。
最初のフェーズでは、 c1≥⋯≥cn となるように変数を並べ替えます。λ=0 で、単一の基本変数 (xh ) があり、その削減コストはゼロでなければならないため、明らかに μ=ch です。これは、 xi の削減コスト ri=ci−λai−μ=ci−ch が ih に対して非負であることを意味します。(3) で与えられる解が実行可能である場合、つまり ∑ih である場合。したがって、二分探索を使用してこのフェーズを完了することができます。n の値が大きいと仮定すると、最初の並べ替えは O(nlogn ) 時間で実行でき、残りのフェーズでは O(logn) 回の反復が必要になり、それぞれに O(n) 時間がかかります。
残念ながら、二分探索を第 2 段階に適用する方法がわかりません。この段階では、ナップザック制約がバインドされ、 λ>0 である解を探します。μ の値を再度検索しますが、今回は単調です。最初に、貪欲なヒューリスティックを問題 (1) に適用し、ナップザック制約を保持しますが、カウント制約を無視します。解がたまたまカウント制約を満たすように発生した場合は、完了です。ただし、ほとんどの場合、カウントの制約に違反します。カウントが b~ を超える場合、(4) の μ の最適値は正であると推測できます。カウントが b~ に満たない場合、μ の最適値は負になります。μ=0 で第 2 フェーズを開始し、最適値の方向に進みます。
貪欲なヒューリスティックはアイテムを c1/a1≥⋯≥cn/an となるようにソートし、 μ=0 から開始するため、現在のソート順は (c1−μ)/a1≥⋯≥(cn−μ)/an になります。 . μ の最適値を検索するときに、その順序を維持します (必要に応じて再ソートします)。混乱を避けるために (願わくば)、μ の最適値は正であると仮定して、μ を増やしていきます。(λ,μ) の値を探します。ここで、x 変数のうちの 2 つが基本であり、つまり、2 つの変数のコストが 0 に削減されています。なら ri=0=rj⟹ci−λai−μ=0=cj−λaj−μ(7)⟹ci−μai=λ=cj−μaj. μ の現在の値に対して (c1−μ)/a1≥⋯≥(cn−μ)/an の場合、μ の次に高い (低い) 値が（7）で同点を作成する場合、連続する連続するアイテムのペア（j = i + 1）が含まれる必要があります。さらに、再び縮退を振り払います (この場合、削減されたコスト 0 の 2 つ以上のアイテムを意味します)。アイテム i と i+1 がコスト 0 を削減した値をわずかに超えて μ を微調整すると、ソート順の唯一の変更はそのアイテムです。 i と i+1 は場所を入れ替えます。その方向にそれ以上移動しないと、i と i+1 が再び同点になりますが、もちろん、いずれかが新しい隣人と同点になる可能性があります。
μ=0 から始まる第 2 フェーズは、次のように進行します。各ペア (i,i+1) について、(ci−μ)/ai=(ci+1−μ)/ai+1 となる μ の値 μi を計算します。その値が μ の現在の値より小さい場合は、その値を ∞ に置き換えます (タイが間違った方向に発生することを示します)。μ を miniμi に更新し、(7) から λ を計算し、(5) と (6) から x を計算します。x が主実行可能 (0≤xi≤ui および 0≤xi+1≤ui+1 に縮小) である場合、停止: x が最適です。それ以外の場合は、i と i+1 をソート順に入れ替え、μi=∞ に設定し (再インデックスされたアイテム i と i+1 は再び結合しません)、μi−1 と μi+1 を再計算します (他の μj はスワップの影響を受けません)。
最初のフェーズで最適値が見つからなかった場合 (および、2 番目のフェーズの開始時の貪欲なヒューリスティックがうまくいかなかった場合)、チェックする μ の値がなくなる前に、2 番目のフェーズを最適値で終了する必要があります (すべての μj= ∞ )。縮退は、コーディングに少し余分な労力をかけるか (たとえば、3 方向以上の関係が発生した場合に第 2 フェーズで i と j の複数の組み合わせをチェックする)、または小さな摂動を作成して縮退を解消することで処理できます。
あなたの質問に対する答えは、いくつかの要因によって異なります。
制約値が非常に大きく (数百万をはるかに超える)、非常に多くの項目 (数千をはるかに超える) がある場合
次に、唯一のオプションは貪欲な近似アルゴリズムです。単位重量あたりの価値の高い順に商品を並べ替え、この順序で梱包します。
単純なアルゴリズムを使用し、高精度を必要としない場合
次に、貪欲なアルゴリズムを使用してみてください。「満足度」自体は非常に大まかな概算である可能性があるため、単純な概算で十分な場合に複雑なソリューションを発明する必要はありません。
制約値が非常に大きい (または連続している) が、アイテムの数がかなり少ない (数千未満) 場合
次に、分岐限定アプローチを使用します。最初から実装する必要はありません。GNU GLPKを試してください。その分岐カット ソルバーは完璧ではありませんが、小さな問題を解決するには十分な場合があります。
制約値も項目数も少ない場合
任意のアプローチを使用します (DP、分岐限定、または単なるブルート フォース)。
制約値が非常に小さい (数百万未満) が、アイテムが多すぎる (数百万のように) 場合
次に、DP アルゴリズムが可能です。
最も単純なケースは、各種類のアイテムのコピー数に上限がない場合の無限ナップザック問題です。このウィキペディアの記事には、問題を単純化する方法についての適切な説明が含まれています: UKPにおける支配関係とその解決方法: Unbounded knapsack problem
より難しいのは、0-1 ナップザック問題で、各種類のアイテムを 0 回または 1 回しか梱包できない場合です。そして、制限されたナップザック問題、各種類のアイテムを整数の制限時間までパックできるようにすることは、さらに困難です。インターネットでは、これらの問題に対する多くの実装が提供されています。同じ記事にいくつかの提案があります。でも、どちらが良いか悪いかはわかりません。