(weight, value)。允许选择不超过 m 个箱子,目标是最大化:
sum(weights_of_chosen) * min(value_of_chosen)。value 从大到小排序,把当前箱子的 value 视作被选集合的最小价值阈值。weight 到一个小根堆(只保留不超过 m 个最大的重量),同时维护堆中重量和 sumW。value 作为最小价值,候选答案为 sumW * value。
这样自然覆盖了选择 1…m 个箱子的所有情况(当堆里元素少于 m 时,即为“少于 m 个”)。小张拥有多箱货物,每箱具有不同的重量和价值。现有一收购商提出,将以最低一箱货物的价值作为整体收购价格,且允许小张最多出售 m 箱货物。请协助小张计算,在此条件下,他能够获得的最大总价值是多少。数值可能较大,最终结果与 1000000007 取余后输出.
总价值的计算方法:m 箱货物的总重量乘上 m 箱货物中价值最小值