你好美妙的社区！
我目前在业余时间写一个小游戏。它发生在一个大星系中，玩家可以控制一些星星。在这些星星上，您可以构建Buildings，每个建筑物都有一定数量（0..*）的输入，并产生一定数量的输出。这些建筑物具有最大容量/吞吐量，并且按比例缩小其输入会按比例缩小其输出。我想找到一种预算算法来优化（或近似）所有建筑物的吞吐量。这似乎是某种最大流量问题，但我读过的流量优化算法都没有不同类型的输入或依赖输出。
我一直在玩的玩具“科技树”是：
Solar plant - None => 2 energy output.
Extractor - 1 energy => 1 ore output
Refinery - 1 energy, 1 ore => 1 metal
Shipyard - 1 metal, 2 energy => 1 ship
我愿意接受次优算法，并且我愿意保证输入/输出没有循环（它们从构建到构建形成 DAG）。这个想法是在没有玩家干预的情况下允许合理的吞吐量和科技树复杂性，因为在数百或数千颗星的规模上，允许玩家手动定义预算策略并不有趣，并且给没有生命的玩家一个独特的优势。
我目前的策略是建立一个有向无环图，给资源一个总排序（船比金属好比矿石比能源好），然后，循环遍历每个资源，找到最“后代”的建筑生产该资源，让它递归地贪婪地从其输入中获取（造船厂将需要 2 能量和 1 金属，然后精炼厂将获取 1 能量和 1 矿石等），然后在图表中找到任何“骗子”（太阳能发电厂提供 4 种能量，最大值为 2 种），缩减其生产并向前传播变化。为 DAG 解决所有问题后，从图中删除终端元素（造船厂），并从建筑物的最大吞吐量中减去每条边的“当前吞吐量”，然后对下一种资源重复该过程。我想如果有更好的方法，我会问比我聪明得多的人。:)