我有一个困扰我的组合问题 . 我希望有人给我他们的想法，并指出我是否遗漏了一些我可能忽略的明显解决方案 .
假设有一家商店从一家供应商处购买所有商品 . 供应商有一个待售物品清单 . 每个项目都具有以下属性：
size, cost, quantity, m, b
m 和 b 是以下等式中的常量：
sales = m * (price) + b
这条线向下倾斜 . 等式告诉我，如果我收取特定价格，我将能够出售多少物品 . 每个项目都有自己的m和b值 .
假设商店的存储空间有限，资金有限 . 该商店希望在其仓库中填写利润最高的物品 .
（顺便说一句，利润密度=利润/规模 . 我定义的是利润密度仅与项目大小有关 . 我可以在尺寸和成本方面考虑密度，但为了做到这一点，我'd have to know the cost of warehouse space. That'不是我目前知道的数字，所以我只想使用尺寸 . ）
物品的利润密度下降越多（见下文） .
如果我翻转线方程式，我可以看到在某段时间内我需要收取哪些价格才能卖出一定数量的物品 .
price = (sales-b)/m
因此，如果我购买n件商品并想要出售所有商品，我必须收费
price = (n-b)/m
这样的收入就是
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更重要 . 因此，这将涉及从当前最有利可图的项目跳到下一项，直到资源耗尽 . 我能做到这一点，但这似乎是一种丑陋的方式 .
我考虑过动态编程，但由于项目的利润密度会根据您购买的金额而变化，因此无法为此提出解决方案 .
我考虑过多元线性回归，并且“考虑”我的意思是我对自己说“多线性回归是一种选择吗？”然后什么也没做 .
我的蜘蛛般的感觉告诉我，有一个更明显的方法盯着我的脸，但我没有看到它 . 请帮助我同时踢自己和facepalm .
2 回答
如果您将此视为多变量优化中的简单练习，其中可控变量是已购买的数量，那么您将根据线性约束优化二次函数 .
如果使用拉格朗日乘数并进行微分，则得到每个涉及自身的量变量的线性方程，并将拉格朗日乘数作为唯一的未知数，并且约束为您提供涉及所有量的单个线性方程 . 因此，将每个数量写为拉格朗日乘数的线性函数，并将其替换为约束方程，以获得拉格朗日乘数中的线性方程 . 解决这个问题然后将拉格朗日乘数插入到更简单的方程中以获得数量 .
如果您可以根据需要购买分数和负数，这可以为您提供解决方案 . 显然你不是，但你可能希望没有什么是非常消极的，你可以围绕非整数数量来得到一个合理的答案 . 如果这对你来说不够好，你可以用它作为分支和绑定的基础 . 如果你假设其中一个数量的 Value 并以这种方式解决其他数量，那么你就得到了可能的最佳答案的上限 - 预测的利润忽略了现实世界对非负性的约束和整数值将永远是至少你必须遵守这些限制所获得的利润 .
您可以将其视为动态编程练习，以充分利用有限的资源 .
举一个简单的例子，考虑只是满足空间约束并忽略成本 . 然后，您希望找到为可用空间带来最大利润的项目 . 选择单位，以便表示用作整数的空间是合理的，然后，对于i = 1到项目的数量，计算出每个空间的整数值，直到极限，选择第一个i项，为该空间量提供最大的回报 . 像往常一样，你可以从i的答案中找出i 1的答案：对于从0到空间限制的每个值，只考虑第i个项目的所有可能数量，直到该空间量，并计算出合并从使用该项目数量返回，然后根据您已经为第一个i项目制定的答案使用剩余空间 . 当我达到项目总数时，您将为您实际想要解决的问题找到最佳回报 .
如果你有空间和成本的约束，那么动态程序的状态不是单个变量（空间）而是一对变量（空间，成本），但你仍然可以解决它，尽管有更多的工作 . 考虑（空间，成本）从（0,0）到实际约束的所有可能值 - 您有一个2维的计算返回表，而不是从0到最大空间的单个值集 . 但是你仍然可以从i = 1到N工作，计算每个限制（空间，成本）的第一个i项目的最高可能回报，并使用i的答案来计算i 1的答案 .