给定竞争有限资源的消费者集合，分配该资源以最大化其适用性

Question

抱歉，问题标题不是很清楚，这是一个很有挑战性的问题，没有提供更具体的例子。考虑以下场景：

我有很多朋友的生日马上就要到了(d1..dn)，我已经设法想出了一些我想以成本价(c1..cn)购买的礼物。不幸的是，我只有一个固定数额的钱(m)，我可以节省下来，每天购买这些礼物。我想问的问题是：

每件礼物的储蓄的理想分布是什么( mi，其中mi的总和来自1..n == m)，以便最小化我朋友的生日和我存足够的钱购买礼物的日期之间的累积偏差。

我正在寻找的是这个问题的解决方案，或者到一个已解决问题的映射，我可以利用它来确定地回答这个问题。感谢您的深思熟虑，如果我能提供任何额外的澄清，请让我知道！

Answer 1

我想你已经说明了背包问题的一种形式，带有一些额外的复杂性-背包问题是NP-完全的( 247页，Garey和Johnson)。基本的背包问题是您有许多对象，每个对象都有一个体积和一个值-您希望用这些对象填充一个固定体积的背包，以便在不超过背包容量的情况下最大化价值。

假设你有阶段(天)和资源(钱)，当你决定购买什么时，资源每天都在变化，这将导致我使用动态编程解决方案技术，而不是直接的优化模型。

你能在评论中澄清“最小化偏差”吗？我不确定我是否理解了这部分。

顺便说一句，mathoverflow.com可能对此没有帮助。如果你看一下算法问题，stackoverflow上有50个，mathoverflow上有50个，你会发现stackoverflow上的问题(和答案)与你正在考虑的问题有更多的共同之处。有一个名为OR Exchange的新网站，但那里的流量还不是很大。