algorithm - 有约束的资源分配算法

Question

我知道有一些算法可以解决我的问题，但我在命名它和相关的解决方案时遇到了问题。这是我的问题:

• 我有一套带钱的钱包
• 我有一组 P 的项目，我可以花钱
• 每个钱包w有一笔钱M，我只能把这笔钱花在几个项目上，而且只能花一定的数额
• 每个项目p需要一笔钱

目标:最大限度地分配我的钱包资金，这样我就可以为我的大部分项目提供资金。

此外，我宁愿让我的所有项目获得 95% 的资金，也不愿让一些项目获得 100% 的资金而其他项目获得 0% 的资金。

所以我想最小化的函数是所有 (d-(all the money allocated to this project))² 假设我没有足够的钱来资助我所有的项目

示例:

我的第一个钱包里有 100 欧元，我可以将 70% 用于项目 1，20% 用于项目 3，10% 用于项目 3

我的第二个钱包有 200 欧元，我可以在项目 1 上花费 30%，在项目 2 上花费 50%，在项目 3 上花费 20%。

关于我的项目:

1. 项目 1 至少需要 120 欧元
2. 项目 2 至少需要 100 欧元
3. 项目 3 至少需要 110 欧元

谢谢你的帮助!

Answer 1

您可以将其表述为最大流问题。将源顶点连接到钱包对应的顶点，其中每条弧的容量是钱包中的金额。将与项目对应的顶点连接到汇点，其中每条弧的容量是该项目所需的资金量。将钱包连接到具有弧线的项目，弧线的容量反射(reflect)了钱包中可用于该项目的金额。

处理分段二次目标有点棘手。幸运的是，它是凸的，所以我敢打赌您可以使用二次规划求解器来获得良好效果。