优化算法问题

这对于那些诀窍家伙来说可能是一个简单的问题。但我无法自己弄清楚。优化算法问题

假设有大量的对象需要我选择。每个对象都有两个已知变量：成本和收益。我有一个预算，比如说1000美元。如何才能找出我应该购买哪些物品，以便在给定预算内最大限度地提高总收益？我想要一个数字优化解决方案。谢谢！

2011-03-29 ZNN

收益是货币吗？或者你是否仅仅在某些任意单位的“利益”中表达利益。如果仅仅是“利益”，@Carl就是钱的现货。如果收益是货币，那么你正在寻找不同的情况，因为收益意味着你会改变你的平衡，因此你可以买得起的成本。 – corsiKa 2011-03-29 23:45:45

我没那么想。这会让问题变得更加复杂。 – ZNN 2011-03-30 01:33:54

你的问题叫做“背包问题”。你可以阅读更多关于wikipedia page。将原始问题的术语翻译成维基百科文章的术语，您的问题的“成本”是背包问题的“重量”。你的问题的“好处”是背包问题的“价值”。

找到一个确切的解决方案是一个NP完全问题，所以如果您有很多对象可供选择，请为慢结果做好准备！

2011-03-29 23:39:30

谢谢！背包问题恰恰是我原来的问题。但是，我的“真正的问题”比这个标准问题有点复杂。我阅读了有关背包问题（动态编程解决方案？）的解决方案，并认为它可能无法解决我的“真正问题”。我将下面的实际问题描述如下。希望你能给我一些关于如何解决它的建议。 – ZNN 2011-03-30 01:44:24

假设每个项目的“价值”不是恒定的。所选项目的总“价值”是所选项目的两个变量（x，y）的函数：Sum（x_i）/ Sum（y_i）。鉴于总重量的限制，如何选择物品以获得最高价值？有关这个问题的任何建议？ – ZNN 2011-03-30 01:57:50

您可能还会考虑Linear Programming。从MathWorld：

简单地说，线性规划是某些设定的使用线性数学模型的约束基础的结果的优化。

2011-03-30 02:16:25 xan

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

这个问题的关键是存储数据，以便您不需要重复计算多次（如果有足够的内存可用）。线性规划有两种常用的方法：自上而下和自下而上。这是一个自下而上的问题。

（一般情况下）查找基本情况值，选择什么是最适合小案例的最佳对象。然后在此基础上构建。如果我们允许自己花更多的钱，那么对于这个小的货币增量来说，最好的组合是什么。可能会采取更多的东西，你以前有过，采取一个新的对象，并取代旧的，采取另一个小物件，仍然会让你在你的预算等。

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

2013-04-23 04:14:20 mNeubauer

回答