フラクショナルナップサック問題：例を使用した欲張りアルゴリズム
サラ・チェン
貪欲な戦略とは何ですか？
貪欲アルゴリズムは、最適な問題を解決するためによく使用される動的プログラミング アルゴリズムに似ています (特定の基準に従って問題の最適な解決策を見つけます)。
貪欲アルゴリズムは、最適なローカル選択を実装し、それらの選択が解決すべき問題に対する最適なグローバル ソリューションにつながることを期待します。貪欲アルゴリズムは、セットアップがそれほど難しくなく、高速です (時間の複雑さは、多くの場合、線形関数または 2 次関数です)。さらに、これらのプログラムはデバッグが難しくなく、メモリ使用量も少なくなります。ただし、結果が常に最適なソリューションになるとは限りません。
貪欲な戦略は、オプション A を構築することによって組み合わせ最適化問題を解決するためによく使用されます。オプション A は、完了するまで (十分な n 個のコンポーネント) A の各コンポーネント Ai を選択することによって構築されます。 それぞれの Ai に対して、最適な Ai を選択します。 このように、最後のステップでは、最後に残った値を受け入れる以外に何も選択できない可能性があります。
貪欲な意思決定には XNUMX つの重要な要素があります。
- 貪欲な選択の方法。現在最適なソリューションを選択し、最後の選択から生じるサブ問題を解決できます。貪欲なアルゴリズムの選択は、以前の選択に依存する場合があります。ただし、将来の選択やサブ問題のソリューションに依存することはできません。アルゴリズムは、ループで選択を行う方法で進化し、同時に、与えられた問題をより小さなサブ問題に縮小します。
- 最適な下部構造。 この問題の最適な解にその部分問題に対する最適な解が含まれている場合、問題の最適な部分構造を実行します。
貪欲アルゴリズムには XNUMX つのコンポーネントがあります。
- ソリューションを作成するための候補のセット。
- ソリューションに追加する最適な候補を選択する選択機能。
- 実行可能関数は、候補をソリューションの構築に使用できるかどうかを決定するために使用されます。
- 解または不完全な解の値を固定する目的関数。
- 完全な解決策が見つかった時期を示す評価関数。
貪欲な者のアイデア
最初のアイデアでは、Greedy One の次の手順に従います。
- 値の非増加順に並べ替えます。
- 順番に注文された荷物を検討し、ナップザックの残りの容量がそれを入れるのに十分な場合は、検討中の荷物をナップザックに入れます（つまり、ナップザックに入れた荷物の合計重量と検討中の荷物の重量が超えないことを意味します）ナップザックの容量）。
ただし、この貪欲なアルゴリズムでは常に最適な解決策が得られるわけではありません。 ここに反例があります:
- 問題のパラメータは次のとおりです。 n = 3; M = 19。
- パッケージ: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> 素晴らしい価値だけでなく、重量も大きいです。
- アルゴリズムは合計値 1 のパッケージ 20 を選択しますが、問題の最適な解決策 (パッケージ 2、パッケージ 3) は合計値 24 で選択されます。
貪欲な二人のアイデア
2 番目のアイデアでは、Greedy Two の次の手順に従います。
- 重みの降らない順に並べ替えます。
- 順番に注文された荷物を検討し、ナップザックの残りの容量がそれを入れるのに十分な場合は、検討中の荷物をナップザックに入れます（つまり、ナップザックに入れた荷物の合計重量と検討中の荷物の重量が超えないことを意味します）ナップザックの容量）。
ただし、この貪欲なアルゴリズムでは常に最適な解決策が得られるわけではありません。 ここに反例があります:
- 問題のパラメータは次のとおりです。 n = 3; M = 11。
- パッケージ: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> 軽量ですが、価値も非常に軽いです。
- アルゴリズムは合計値 1 の (パッケージ 2、パッケージ 26) を選択しますが、問題の最適解は合計値 3 の (パッケージ 28) です。
貪欲なXNUMX人のアイデア
3 番目のアイデアでは、貪欲法 3 の次の手順に従います。実際、これは最も広く使用されているアルゴリズムです。
- パッケージを単価の高くない順に並べ替えます
。 あなたが持っている：
- 順番に注文された荷物を検討し、ナップザックの残りの容量がそれを入れるのに十分な場合は、検討中の荷物をナップザックに入れます（つまり、ナップザックに入れた荷物の合計重量と検討中の荷物の重量が超えないことを意味します）ナップザックの容量）。
アイデア: この問題の貪欲なアイデアは、 
それぞれの比率 
。 次に、これらの比率を降順に並べ替えます。 一番高いものを選ぶでしょう パッケージとそのパッケージを含めることができるナップザックの容量 (残り > wi）。 ナップザックに荷物を入れるたびに、ナップザックの容量も減っていきます。
パッケージの選択方法:
- 一連の単位コストを考慮してください。 単価の減少に従ってパッケージを選択します。
- 部分的な解決策が見つかったとします: (x1、…、 バツi).
- ナップザックの値は次のように取得されます。
- ナップザックに入れた荷物の重さに応じて：
- したがって、ナップザックの残り重量制限は次のようになります。
アルゴリズムのステップ
これは最大値を求める問題であることがわかります。 パッケージのリストは、分岐を考慮するために単価の降順に並べ替えられます。
- ステップ 1: ノード ルートは、パッケージが選択されていないナップザックの初期状態を表します。
- 合計値 = 0。
- ルート ノードの上限 UpperBound = M * 最大単位コスト。
- ステップ 2: ノード ルートには、最大の単位コストのパッケージを選択する機能に対応する子ノードがあります。 ノードごとにパラメータを再計算します。
- TotalValue = TotalValue (古い) + 選択したパッケージの数 * 各パッケージの値。
- M = M (旧) – 選択したパッケージの数 * 各パッケージの重量。
- UpperBound = TotalValue + M (新規) * 次に考慮されるパッケージの単価。
- ステップ 3: 子ノードでは、上限が大きいノードの分岐を優先します。 このノードの子は、単価の大きい次のパッケージを選択する機能に対応します。 各ノードについて、手順 2 で説明した式に従ってパラメーター TotalValue、M、UpperBound を再計算する必要があります。
- ステップ 4: ステップ 3 を繰り返しますが、上限が見つかったオプションの一時的な最大コスト以下の値であるノードについては、そのノードについて分岐する必要はありません。
- ステップ 5: すべてのノードが分岐または切断されている場合、最も高価なオプションが検索対象となります。
アルゴリズムの疑似コード:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
アルゴリズムの複雑さ:
- 単純なソートアルゴリズム（選択、バブルなど）を使用する場合、問題全体の複雑さは O(n2) になります。
- クイックソートまたはマージソートを使用する場合、問題全体の複雑さは O(nlogn) になります。
Java 貪欲な3人のコード
- まず、KnapsackPackage クラスを定義します。 このクラスには、各パッケージの重量、値、および対応するコストのプロパティがあります。 このクラスのプロパティ コストは、メイン アルゴリズムのソート タスクに使用されます。 各コストの値は、
各パッケージの比率。
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- 次に、アルゴリズム Greedy Three を実行する関数を作成します。
public void knapsackGreProc(int W[], int V[], int M, int n) {
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int i = 0; i < n; i ++) {
packs[i] = new KnapsackPackage(W[i], V[i]);
}
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
コードの説明：
- 各ナップザック パッケージの重量と値を初期化します。
- ナップザック パッケージをコストの降順で並べ替えます。
- パッケージ i を選択した場合。
- パッケージの数を選択する場合は i で十分です。
- すべてのパッケージを参照するときに停止します。
このチュートリアルには XNUMX つの例があります。 上記のプログラムを実行する Java コードと XNUMX つの例を次に示します。
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
出力は次のようになります。
- 最初の例:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- XNUMX 番目の例:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
最初の例を分析します。
- 問題のパラメータは次のとおりです。 n = 4; M = 37。
- パッケージ: {i = 1; W[i] = 15; V[i] = 30; コスト = 2.0}; {i = 2; W[i] = 10; V[i] = 25; コスト = 2.5}; {i = 3; W[i] = 2; V[i] = 4; コスト = 1.0}; {i = 4; W[i] = 4; V[i] = 6; コスト = 1.5}。
- 単価の値が増加しない順にパッケージを並べ替えます。 あなたは次のものを持っています: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}。
最初の例のアルゴリズムを適用する手順は次のとおりです。
- x1、x2、x3、x4 は、パッケージ {i = 2} に対応する、選択された各パッケージの番号であると定義します。 -> {i = 1} -> {i = 4} -> {i = 3}。
- ノード ルート N は、パッケージを選択していない状態を表します。 それから：
- 合計値 = 0。
- M = 37 (提案通り)。
- UpperBound = 37 * 2.5 = 92.5、そのうち 37 が M、2.5 がパッケージ {i = 2} の単価です。
- パッケージ {i = 2} の場合、4 つの可能性があります。 3 つのパッケージ {i = 2} (x1 = 3) を選択します。 2 パッケージを選択 {i = 2} (x1 = 2); 1 つのパッケージ {i = 2} (x1 = 1) を選択し、パッケージ {i = 2} (x1 = 0) を選択しません。 これら 4 つの可能性に従って、ルート ノード N を 4 つの子 N[1]、N[2]、N[3]、および N[4] に分岐します。
- 子ノード N1 には、次のものがあります。
- TotalValue = 0 + 3 * 25 = 75。ここで、3 は選択されたパッケージ {i = 2} の数、25 は各パッケージ {i = 2} の値です。
- M = 37 – 3 * 10 = 7。ここで、37 はナップザックの初期数量、3 は荷物の数 {i = 2}、10 は各荷物の重量 {i = 2} です。
- UpperBound = 75 + 7 * 2 = 89。ここで、75 は TotalValue、7 はナップサックの残りの重量、2 はパッケージの単価です {i = 1}。
- 同様に、ノード N[2]、N[3]、および N[4] のパラメーターを計算できます。UpperBound はそれぞれ 84、79、および 74 です。
- ノード N[1]、N[2]、N[3]、および N[4] のうち、ノード N[1] が最大の UpperBound を持っているため、ノード N[1] を最初に分岐します。この方向からの良い計画。
- ノード N[1] からは、x1 = 1 に対応する子ノード N[2-0] が 7 つだけあります (バックパックの残りの重量は 1 ですが、各パッケージ {i = 15} の重量は 1 であるため)。 。 N[1-1] ボタンのパラメータを決定すると、N[1-85.5] の UpperBound は XNUMX になります。
- ノード N[1-1] の分岐を続けます。 ノード N[1-1] には、x2 = 1 および x1 = 1 に対応する 1 つの子 N[1-2-3] および N[1-3-0] があります。これら 1 つのノードのパラメーターを決定すると、 N[1-1-84] の UpperBoundary は 1、N[1-2-82] の UpperBoundary は 1 であるため、ノード N[1-1-XNUMX] の分岐を続けます。
- ノード N[1-1-1] には、x1 = 1 と x1 = 1 に対応する 1 つの子 N[1-1-2-4] と N[1-4-0-1] があります。これらは 1 つのリーフ ノードです。 (オプションを表す) 各ノードに対してパッケージの数が選択されているためです。 ここで、ノード N[1-1-1-3] は 2 のオプション x0 = 3、x1 = 4、x1 = 83、および x1 = 1 を表し、ノード N[1-2-1-3] はオプション x2 を表します。 = 0、x3 = 1、x4 = 01、x81 = 83 で XNUMX になります。したがって、ここでの一時的な最大値は XNUMX になります。
- ノード N[1-1-2] に戻ると、N[1-1-2] の UpperBound が 82 < 83 であることがわかります。そのため、ノード N[1-1-2] をトリムします。
- ノード N2 に戻ると、N2 の UpperBound が 84 > 83 であることがわかります。そのため、ノード N2 の分岐を続けます。 ノード N2 には、x2 = 1 および x2 = 2 に対応する 2 つの子 N[1-2] および N[0-2] があります。N[1-2] および N[2-2] のパラメーターを計算すると、次のようになります。 N[1-83] の上限は 2、N[2-75.25] の上限は 83 です。 これらの値はどちらも XNUMX より大きくないため、両方のノードがトリミングされます。
- 最後に、ノード N3 と N4 もトリミングされます。
- したがって、ツリー上のすべてのノードは分岐またはトリミングされるため、最適な一時的な解決策を探す必要があります。 したがって、合計値が 3、合計重量が 2 の 1 つのパッケージ {i = 4}、3 つのパッケージ {i = 83}、および 36 つのパッケージ {i = XNUMX} を選択する必要があります。
4 番目の例と同じ分析を行うと、パッケージ 3 (5 回) とパッケージ 3 (XNUMX 回) を選択するという結果が得られます。
Python3 は貪欲な XNUMX のコード
- まず、KnapsackPackage クラスを定義します。
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
- 次に、アルゴリズム Greedy Three を実行する関数を作成します。
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
コードの説明：
- 各ナップザック パッケージの重量と値を初期化します。
- ナップザック パッケージをコストの降順で並べ替えます。
- パッケージ i を選択した場合。
- パッケージの数を選択する場合は i で十分です。
- すべてのパッケージを参照するときに停止します。
ここにある Python最初の例で上記のプログラムを実行する 3 つのコード:
if __name__ == "__main__":
W = [15, 10, 2, 4]
V = [30, 25, 2, 6]
M = 37
n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
出力は次のようになります。
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Greedy Three の C# コード
- まず、KnapsackPackage クラスを定義します。
using System;
namespace KnapsackProblem
{
public class KnapsackPackage
{
private double weight;
private double value;
private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- 次に、アルゴリズム Greedy Three を実行する関数を作成します。
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
コードの説明：
- 各ナップザック パッケージの重量と値を初期化します。
- ナップザック パッケージをコストの降順で並べ替えます。
- パッケージ i を選択した場合。
- パッケージの数を選択する場合は i で十分です。
- すべてのパッケージを参照するときに停止します。
最初の例で上記のプログラムを実行する C# コードを次に示します。
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
出力は次のようになります。
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Greedy Three の反例
Greedy Three のアルゴリズムは迅速に解決され、場合によっては最適化されることもあります。 ただし、一部の特殊なケースでは、最適な解決策が得られないことがあります。 ここに反例があります:
- 問題のパラメータは次のとおりです。 n = 3; M = 10。
- パッケージ: {i = 1; W[i] = 7; V[i] = 9; コスト = 9/7}; {i = 2; W[i] = 6; V[i] = 6; コスト = 1}; {i = 3; W[i] = 4; V[i] = 4; コスト = 1}。
- アルゴリズムは合計値 1 の (パッケージ 9) を選択しますが、問題の最適解は合計値 2 の (パッケージ 3、パッケージ 10) です。
上記のプログラムを反例とともに実行する Java コードを次に示します。
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
結果は次のとおりです。
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
分数ナップザック問題は以上です。
