algorithm - 如何以最有效的方式计算出利润最密集的组合？

Question

我有一个困扰我的组合问题。我希望有人能给我他们的想法，并指出我是否遗漏了一些我可能忽略的明显解决方案。

假设有一家商店从一家供应商那里购买所有用品。供应商有一份待售元素 list 。每个项目都有以下属性:

size, cost, quantity, m, b

m 和 b 是以下等式中的常数:

sales = m * (price) + b

这条线向下倾斜。该等式告诉我，如果我收取特定价格，我将能够销售多少该商品。每个项目都有自己的 m 和 b 值。

假设商店的存储空间和资金有限。商店希望尽可能用利润最密集的商品填满其仓库。

(顺便说一下，利润密度 = 利润/规模。我定义的利润密度仅与项目规模有关。我可以根据规模和成本来处理密度，但要做到这一点，我必须知道仓库空间的成本。这不是我目前知道的数字，所以我将只使用大小。)

商品的利润密度越买越低(见下文。)

如果我翻转线方程，我可以看到在给定时间段内销售给定数量的商品我必须收取什么价格。

price = (sales-b)/m

所以如果我买了 n 件商品并想全部卖掉，我就必须收费

price = (n-b)/m

这样的 yield 是

price*n = n*(n-b)/m

利润是

price*n-n*cost = n*(n-b)/m - n*cost

利润密度为

(n*(n-b)/m - n*cost)/(n*size)

或者，等价地

((n-b)/m - cost)/size

假设我有一个表格，其中包含每个可用项目以及每个项目的利润密度。

问题是，为了最大限度地提高商店的收入，我应该购买多少件商品？

一种可能性是在成本和空间范围内生成所有可能的项目组合，并选择盈利能力最高的组合。在 1000 个项目的列表中，这花费的时间太长了。 (我试过这个，1000 个列表花了 17 秒。太可怕了。)

我(在纸面上)尝试的另一个选择是选择列表中最赚钱的前两个项目。我们将利润最高的项目称为 A，将利润第二高的项目称为 B，并将利润第三高的项目称为 C。我尽可能多地购买项目 A，直到它的利润低于项目 B。然后我使用 B 重复此过程和 C，对于列表中的每个项目。

然而，情况可能是这样的，在购买项目 B 之后，项目 A 再次成为最赚钱的项目，超过 C。因此这将涉及从当前最赚钱的项目跳到下一个，直到资源耗尽。我可以做到这一点，但这似乎是一种丑陋的方式。

我考虑过动态规划，但由于商品的利润密度会根据您购买的数量而变化，因此我无法为此提出解决方案。

我考虑过多元线性回归，“考虑”是指我对自己说“多元线性回归是一种选择吗？”然后什么都不做。

我的蜘蛛侠直觉告诉我，有一种更明显的方法正盯着我，但我没有看到。请帮我同时踢自己和脸。

Answer 1

如果您将此视为多元优化中的一个简单练习，其中可控变量是购买的数量，那么您就是在优化受线性约束约束的二次函数。

如果您使用拉格朗日乘数并进行微分，那么您会得到一个包含自身的每个量变量的线性方程，拉格朗日乘数作为唯一的未知数，并且约束会为您提供一个包含所有量的线性方程。所以将每个量写成拉格朗日乘数的线性函数代入约束方程得到拉格朗日乘数中的线性方程。解决这个问题，然后将拉格朗日乘数代入更简单的方程以获得数量。

如果需要，您可以购买小数和负数量的东西，这为您提供了一个解决方案。显然你不是，但你可能希望没有什么是非常负面的，你可以四舍五入非整数数量以获得合理的答案。如果这对您来说还不够好，您可以将其用作分支定界法的基础。如果您对其中一个数量的值做出假设并以这种方式求解其他数量，您将获得可能的最佳答案的上限 - 忽略现实世界对非负性和整数值的限制的预测利润将始终是如果您必须遵守这些限制，至少要赚取利润。