algorithm - 重要度を最大化する分枝限定アルゴリズム

Question

分岐限定アルゴリズムで解決すべき問題がありますが、解決方法を考えるのに苦労しています。分岐限定アルゴリズムを開始する方法がわかりません。

問題は次のとおりです。

車には最大重量と容積容量があり、車に荷物を詰める必要があります。これらのパッケージには、重要性、重量、および容積の決定された値があります。目的は、車の重量と容積の制限を超えずに、重要度が最も高いパッケージの組み合わせを車に搭載することです。

Answer 1

分枝限定については、部分的な解を記述する方法と、それがどれほど優れているかについての限界を計算する方法を知る必要があります。部分的な解決策は、他に何を追加するかに関係なく、確実に車に搭載されると判断したパッケージのリストです。どのくらいのスペースと重量が残っているか、残っているパッケージの中で、単位体積あたりの価値と単位あたりの価値の最大額を確認することで、車の価値の上限を計算できます。重量は。