オブジェクトスタッキング、動的プログラミング

Question

私は動的プログラミングアルゴリズムで解決できるボックススタッキング問題に似た問題を扱っています。私はここでそれについての記事を読んでいますが、私はDPアプローチを理解するのは難しいですし、それがどのように機能するのかについていくつか説明したいと思います。ここでの問題は手元にあります：

Xのオブジェクトを考える

、自重「W」と強度「S」、どのよう 多くは、あなたが互いの上に積み重ねることが可能で、各？ の体重は、その体重を上回っていても、その体重の合計は、 の体重を超えていない限り、持ち運びできます。

私は、それが最適な部分構造を持っているが、私を混乱させる部分的な部分問題があることを理解します。私はそれが何回も同じことを計算するかを見るために再帰ツリーを作成しようとしていますが、関数が例えば1つまたは2つのパラメータを取るかどうかわかりません。

Answer 1

この問題を解決するための第一歩は、最高から最低の強度の順に並べられたボックスで最適なスタックを見つけることができることを証明しています。

次に、強度でボックスをソートし、最適なスタックに含まれているものを特定するだけです。

再帰的サブ問題には2つのパラメータがあります。スタックの最上部に置くことができる最善のスタックを見つけます。

Answer 2

良いDPソリューションが存在する場合、それは2つのparamsを取る：未訪問のオブジェクトの

• 訪問したオブジェクトの数や、未訪問のオブジェクトの数
• 総重量あなたが現在訪問したオブジェクトの（重量余裕が問題ではありません。 ）

動作させるには、次のオブジェクトの上にオブジェクトを配置することは役に立たない、順序を見つける必要があります。つまり、この順序付けに違反するすべてのソリューションに対して、この順序付けに従うもう1つのソリューションがあり、それはより良いか同等です。

選択した注文が存在することを証明し、明確に定義する必要があります。体重には何らかの意味があるので、Matt Timmermansによって提案された、力による単純なソートは十分ではないと思います。しかしそれは校正部分です...