コンテンツ
- 定義-ナップザック問題とはどういう意味ですか？
- Microsoft AzureとMicrosoft Cloudの紹介|このガイドを通して、クラウドコンピューティングとは何か、Microsoft Azureを使用してクラウドからビジネスを移行および実行する方法を学習します。
- Techopediaはナップザック問題を説明します
定義-ナップザック問題とはどういう意味ですか？
ナップザック問題は、問題と解決策の両方を説明するために使用される最適化問題です。その名前は、固定サイズのナップザックの中に置くことができるアイテムの数に制約があるというシナリオに由来しています。特定の重みと値を持つアイテムのセットが与えられた場合、その目的は、ナップザックの重みの制約を考慮して、できるだけ多くの値をナップザックに入れることです。
Microsoft AzureとMicrosoft Cloudの紹介|このガイドを通して、クラウドコンピューティングとは何か、Microsoft Azureを使用してクラウドからビジネスを移行および実行する方法を学習します。
Techopediaはナップザック問題を説明します
ナップザック問題は、組み合わせ最適化問題の例であり、数学とコンピューターサイエンスで、オブジェクトのセットから最適なオブジェクトを見つけることに関するトピックです。これは1世紀以上にわたって研究されてきた問題であり、コンビナトリアル最適化でよく使用される問題例です。徹底的な検索が不可能な最適なオブジェクトまたは有限解が必要な場合です。この問題は、財政的制約や投資やポートフォリオの選択におけるリソース割り当てなど、現実のシナリオで見つけることができます。また、応用数学、複雑性理論、暗号法、組み合わせ論、コンピューターサイエンスなどの分野でも見られます。これは、ロジスティクスで最も重要な問題です。
ナップザック問題では、指定されたアイテムには少なくとも2つの属性があります。重要度に影響するアイテムの値と、制限の側面であるアイテムの重量または体積です。徹底的な検索は不可能であるため、問題をより小さなサブ問題に分割し、再帰的に実行できます。これは最適な部分構造と呼ばれます。これは、一度に1つのアイテムのみを処理し、ナップザックで現在使用可能な重量を引き続き処理します。問題解決者は、まだ受け入れられる重量に基づいて、アイテムをとるかどうかを決定するだけです。ただし、プログラムの場合、再計算は独立しておらず、問題を引き起こす可能性があります。これは、動的プログラミング手法を適用できる場所です。各副問題の解は保存されているため、計算は一度だけで済みます。