从N个不同价格栈购买K物品的最低成本

Question

有些物品有许多箱子。

每个框：可以有不同数量的项目。每个项目都有不同的成本。

你必须买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 =购买从顶部=> (1x4=4)、(2x3=6)、(3x1=3) =成本= 13的第三个完整框。

StackB =购买第一个盒子=> (4x1=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整箱，然后从第二=> 79 x1=79购买79，=成本= 179

购买80件商品的总最低成本为179

Answer 1

预处理：

为每个堆栈创建一个数组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

注意，这将从动态规划中受益:回溯给定限制和堆栈位置的最小成本。

优化

我认为，您将找到一个更有效的攻击方法，方法是对堆栈进行平分，并逐步为左边的quant项和右边的limit-quant项找到最佳解决方案，以便quant遍历允许的范围。这允许您通过二分法进行重复，并为您提供了对单个项更改进行增量估计的路径。您可以自下而上地回忆部分结果，在较小的时间复杂度中找到最优的解决方案。