価格が異なるN個のスタックからK個のアイテムを購入するための最小コスト

Question

いくつかのアイテムのN個のスタックがあります。

各ボックス：異なる数のアイテムを持つことができます。 アイテムごとに異なるコストを設定できます。

あなたはK個のアイテムを購入する必要があります。 すべての箱は積み重ねられています。つまり、上から購入して下に進むことができます。

合計費用が最小になるようにKアイテムを最適に購入するにはどうすればよいですか？ （私たちは、あなたが部分的ボックスを購入することができると仮定することができる）

例1：

StackA = [1,4]、[2,3]、[5,1]、[10]、[ 50]、[1,5]

StackB = [4,1]、[6,7]、[2,3]、[14,7]、[6,1]、[19,4]

K = 10

[X、Y] = [アイテムごとのボックス内のアイテムの数、コスト]

最適購入は次のようになります

StackA =購入2からの完全なボックス上から部分的に第1 => （ X4 = 4）、（ X3 = 6）、（ X1 = 3）=コスト=

StackB =最初のボックスを購入=> （ x1 = 4）=>コスト= 4

10個のアイテムを購入するための総コストが最小になるであろう4 + 13 = 17

実施例2：

StackA = [1、100] 、[100 1]

StackB = [10,1]、[6]、[15]、[25、30]、[15]、[2]、[60、1]、[19]、[4]

K = 80

最適な買いは次のようになります。

StackA =購入1つのボックス全体と第二=> （×100 = 100）、（×1 = 79）、=コスト= 179

から79を買います

80個のアイテムを購入するための総コスト最小は179

Answer 1

プリプロセスのようになります。

M各スタックの配列cost、長さK、ここでcost[i]は、そのスタックから上位iアイテムを購入するコストです。

計算：

この動的プログラミング恩恵を受ける再帰...

function stack_cost(stack_list, limit, subtotal) 
// stack_list list of stacks and cost array of each 
// limit   remaining quantity of items to buy 
// subtotal  cost so far 

best_cost = +Inf 

for quant in range [0:limit] 
    // Buy the top "quant" items from this stack, 
    // and move on to the next. 
    total = stack_cost(stack_list[1: ], 
         limit - quant, 
         subtotal + stack_list[0].cost[quant]) 
    if total < best_cost 
     total = best_cost 
     // save solution as needed 

注定義：指定された限界とスタックの位置に対する最小コストをmemoize。私はあなたがquantが許可を反復処理するために、スタックを二等分し、インクリメンタル左側のquant項目、右側にlimit-quant項目のための最善の解決策を見つけることによって、より効率的な攻撃を見つけることだと思う

最適化

範囲。これにより、二分法で再帰することができ、1つのアイテムの変更に対して増分見積もりを行うためのパスが提供されます。部分的な結果をボトムアップでメモして、より短時間で複雑な最適解を見つけることができます。