优化算法问题

Question

对于那些有经验的人来说，这可能是一个简单的问题。但我自己想不出来。

假设有大量的对象需要我从中选择一些。每个对象都有两个已知变量:成本和收益。我有一个预算，比如说1000美元。我如何才能知道我应该购买哪些物品，以便在给定的预算内实现总收益的最大化？我想要一个数值优化解决方案。谢谢!

Answer 1

你的问题被称为“背包问题”。你可以在wikipedia page上阅读更多。将你最初问题的命名法翻译成维基百科文章的命名法，你的问题的“成本”就是背包问题的“权重”。你的问题的“好处”就是背包问题的“价值”。

找到精确的解决方案是一个NP完全的问题，所以如果你有很多对象可供选择，那么要准备好慢的结果！

Answer 2

您还可以研究一下Linear Programming。来自MathWorld：

简单地说，线性规划就是使用线性数学模型，根据一组约束条件对结果进行优化。

Answer 3

是的，如前所述，这是背包问题，我会选择使用线性规划。

这个问题的关键是存储数据，这样您就不需要重新计算一次以上(如果有足够的内存可用)。关于线性规划，一般有两种方法:自上而下和自下而上。这是一个自下而上的问题。

(通常)查找基本情况值，对于小情况，选择最优的对象是什么。然后在此基础上进行构建。如果我们允许自己花更多的钱，那么对于这点钱的增量来说，什么是最好的对象组合。可能的情况是，更多地使用你以前拥有的东西，使用一个新的对象并替换旧的对象，使用另一个小对象，使您仍然保持在您的预算之内等等。

就像我说的，主要的想法是不重新计算值。如果你遵循这个模式，你会得到一个很高的数字，并发现为了购买价值X美元的商品，最好的解决方案是将你在两个较小的情况下拥有的东西结合起来。