1

抱歉,问题标题不是很清楚,这是一个具有挑战性的问题,无需提供更具体的示例。考虑以下场景:

我有一些朋友的生日即将到来(d1..dn),我设法想出了一些我想以成本购买他们的礼物(c1..cn)。不幸的是,我每天只能存下固定数量的钱(m)来购买这些礼物。我想问的问题是:

什么是每件礼物的理想储蓄分配(mi,其中 mi 从 1..n == m 的总和)以最小化我朋友的生日和我存够钱的日期之间的总偏差购买该礼物。

我正在寻找的不是这个问题的解决方案,就是我可以用来确定性地回答这个问题的已解决问题的映射。感谢您的思考,如果我能提供任何额外的说明,请告诉我!

4

1 回答 1

0

我认为您已经陈述了一种带有一些额外复杂性的背包问题 - 背包问题是 NP-Complete(第 247 页,Garey 和 Johnson)。基本的背包问题是您有许多对象,每个对象都有一个体积和一个值 - 您想用对象填充一个固定体积的背包,以在不超过背包容量的情况下最大化值。

鉴于您有阶段(天)和资源(金钱),并且在您决定购买什么时资源每天都在变化,这将导致我采用动态编程解决方案技术,而不是直接优化模型。

您能否在评论中澄清“最小化偏差”?我不确定我是否理解那部分。

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

于 2010-02-19T20:01:14.667 回答