php – 通过向多个买家销售商品来查找最高总价,受限于用户输入

编辑：我很抱歉,我对这个问题的解释并不清楚！这应该更好：

>用户发送文章的ID号和最大值.捆绑(包裹)数量
> API搜索文章可用的所有价格,并计算最佳结果.捆绑数量(限制为客户提供的最大数量)
ONE Bundle是送到ONE平台的一件物品(买家)

谢谢！

解决方法:

这是一个有趣的小问题.今天早上我花了几个小时就完成了,虽然我没有完整的解决方案,但我认为我已经足够让你开始了(我认为这就是你所要求的).

首先,我根据你对问题的描述假设这些东西：

>所有买家都报出所有商品的价格
>没有关于这些项目的假设,它们可能都是不同的
>用户只能与有限数量的买家互动
>用户想要将每件商品卖给一个买家
>用户可以向单个买方出售多个商品

精确的解决方案 – 蛮力方法

为此,首先要意识到的是,对于给定的一组买家,可以直接计算最大总收入,因为您可以选择每个项目的买家组中提供的最高价格.加上所有这些最高价格,您就拥有该组买家的最大总收入.

现在,您所要做的就是为每个可能的买家组合进行计算.这是一个基本的组合问题：“n选择k”,其中n是买家总数,k是您受限的买家数量.有些功能会生成这些组合的列表(我自己编写了……还有this PEAR package for PHP).

一旦您为所选买家的每个组合获得最大总收入,只需选择最大的一个,您就解决了问题.

更优雅的算法？

然而,正如我通过称之为“蛮力”所暗示的那样,上述情况并不快,并且可怕地扩展.我的机器耗尽内存,有20个买家和20个项目.我确信存在一个更好的算法,而且我有一个很好的算法,但它并不完美.

这是基于机会成本.我计算每个项目的最高价格和第二高价格之间的差异.这种差异是不以最高价格挑选买方的机会成本.

然后我选择为机会成本最高的项目提供高价的买家(从而避免最差的机会成本),直到我有k-1买家(其中k是我能选择的最大值).最后的选择很棘手,而不是写一个更复杂的算法,我只是为最终买家运行所有可能性并选择最佳收入.

这种策略在大多数时候都会选择最好的组合,如果它错过了,它就不会错过太多.它也相对较好地扩展.它比小尺度上的蛮力快10倍,如果我将所有参数(买家,买家限制和物品)增加四倍,计算时间就会增加20倍.考虑到涉及多少组合,这非常好.

我已经起草了一些代码,但这篇文章太长了.如果您有兴趣,请告诉我,我会想办法将它发送给您.

（编辑：北几岛）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!