C++ の分数ナップザック問題とは、バッグに最大値を超えずに最大値が含まれるように、指定された重量と利益のアイテムをバッグに詰める方法を特定することを指します。
C++ で分数ナップザック問題を解決する方法
それぞれが指定された重量と利益を持つアイテムのセットが与えられると、アイテムの合計重量がバッグの最大制限よりも小さくなるように組み合わせてアイテムの各数を決定しますが、その値はできるだけ大きく保つ必要があります。
分数ナップザック問題を実装するアルゴリズム
ナップザック アルゴリズムの機能は、次の点から理解できます。
- 重みと利益の 2 つの配列を取得します。
- 最大サック値を W に設定します。
- 両方のパラメータの比率を取得して密度を決定します。
- 項目を密度の降順に並べ替えます。
- <=W になるまで値を加算します。
分数ナップザック問題を解決するための貪欲なアプローチ
貪欲なアプローチは、各ステップで理想的な選択を行い、最終的に理想的なソリューションに導くことを目的としています。最終的に結果だけを結論付けるのではなく、結論に至るまで段階的に問題を解決します。これは、C++ で分数ナップザック問題の解決策を実装するためのソース コードです。
#include
を使用して 名前空間 標準 ;
構造体 物体 {
整数 価値、重量 ;
物体 ( 整数 価値、 整数 重さ )
: 価値 ( 価値 ) 、 重さ ( 重さ )
{
}
} ;
ブール cmp ( 構造体 オブジェクト x、 構造体 オブジェクトy )
{
ダブル A1 = ( ダブル ) バツ。 価値 / バツ。 重さ ;
ダブル A2 = ( ダブル ) そして。 価値 / そして。 重さ ;
戻る A1 > A2 ;
}
ダブル フラクショナルナップザック ( 構造体 オブジェクト配列 [ 】 、
整数 で、 整数 サイズ )
{
選別 ( ああ、ああ + サイズ、センチメートル ) ;
整数 curweight = 0 ;
ダブル 最終値 = 0.0 ;
のために ( 整数 私 = 0 ; 私 < サイズ ; 私 ++ ) {
もし ( curweight + 到着しました [ 私 】 。 重さ <= で ) {
curweight + = 到着しました [ 私 】 。 重さ ;
最終値 + = 到着しました [ 私 】 。 価値 ;
}
それ以外 {
整数 残る = で - curweight ;
最終値 + = 到着しました [ 私 】 。 価値
* ( ( ダブル ) 残る
/ 到着しました [ 私 】 。 重さ ) ;
壊す ;
}
}
戻る 最終値 ;
}
整数 で = 60 ;
オブジェクト配列 [ 】 = { { 100 、 二十 } 、
{ 380 、 40 } 、
{ 140 、 10 } 、
{ 180 、 30 } } ;
整数 サイズ = のサイズ ( 到着しました ) / のサイズ ( 到着しました [ 0 】 ) ;
コート << 「最大利益 = 」
<< フラクショナルナップザック ( arr、v、サイズ ) ;
戻る 0 ;
}
このコードでは、重みと利益の値が格納されたオブジェクト構造が定義されています。 bool cmp() は、2 つのオブジェクトの重みと値の比率に基づいて 2 つのオブジェクトを比較するために使用されます。配列は降順に配置され、値は最大値に達するまで追加され続けます。現在の値が許容され、制限内にある場合はその値が追加され、そうでない場合はその減少した比率がバッグに追加されます。重量と値の大きさがメインコードに入力され、最大利益が出力に表示されます。
スナックに保存された最大利益は 580 です。
結論
C++ の分数ナップザック問題とは、バッグに最大値を超えずに最大値が含まれるように、指定された重量と利益のアイテムをバッグに詰める方法を特定することを指します。これは、各ステップで理想的な選択を行い、最終的に理想的なソリューションに導くことを目的とした貪欲なアプローチによって実現できます。