これは、Kleinberg と Tardos による Algorithm Design の追加メモとして見つけた問題です。
コストが 100 ドルから始まり、1 か月あたり r i < 1の係数で減価する機器を売却しようとしていると仮定すると、今から t か月後にそれを売却すると、100.r i tを受け取ることになります。
1 か月に 1 つのアイテムしか販売できない場合、それらを販売する最適な順序は何ですか?
入力 (3/4; 1/2; 1/100)
最適な順序は [100x{1/2+(3/4) 2 +(1/100) 3 }] です。
この問題にどう対処すればよいかわかりません。
貪欲な方法が機能するはずです。毎月、Ri^month - Ri^(month+1) を最大化するアイテムを販売します。これは、翌月に最も価値を失うアイテムを販売することを意味します。
入力例では:
したがって、最初の月は R = 1/2 のアイテムを販売します
R = 2 番目の項目として 3/4、最後に 1/100。
私は数学者ではないので証明はできませんが、a^xa^(x+1) = b^xb^(x+1) という形式の関数が1つのソリューション。
個々のRiを持つアイテムがN個あるとします。
Cij = Power(Ri,j) である N x N 行列を計算します。
問題は、N 個のオブジェクトが N 個の位置に配置され、それぞれに対応する利益が関連付けられている割り当て問題に要約されます。
Hungarian Algorithm などのアルゴリズムを使用して、総利益を最大化します。