想象一下，我是一家面包店，试图用我有限的原料来最大化馅饼的数量。
以下馅饼配方中的每一个都能精确地制作一个馅饼：
A = i + j + k
B = t + z
C = 2z
D = 2j + 2k
*食谱总是有线性的形式，如上图所示。
我有以下成分：
4 of i
5 of z
4 of j
2 of k
1 of t
我想要一个算法，使我的馅饼产量最大化，因为我的配料有限。
这些示例输入的最优解将产生以下数量的pie：
2 x A
1 x B
2 x C
0 x D
= a total of 5 pies
我可以用所有组合的最大生产者来解决这个问题，但是这个数字
随着配料数量的增加，组合的数量变得越来越高。我觉得必须
作为这类优化问题的推广，我只是不知道从哪里开始。
虽然我只能烤整个馅饼，但我仍然有兴趣看到一种可能产生非整数结果的方法。
最佳答案
您可以定义linear programming问题。我将在示例中展示用法，但它当然可以推广到任何数据。
将pie表示为变量（x1=a，x2=b，…），lp问题如下：
maximize x1 + x2 + x3 + x4
s.t. x1 <= 4 (needed i's)
x1 + 2x4 <= 4 (needed j's)
x1 + 2x4 <= 2 (needed k's)
x2 <= 1 (needed t's)
x2 + 2x3 <= 5 (needed z's)
and x1,x2,x3,x4 >= 0
该问题的分式解是多项式可解的，而整数线性规划是NP完全的。
这个问题确实是“AA>”，因为给定了一个“AA>问题”，你可以用同样的方法来减少问题，使“馅饼的数量最大化”，其中每个约束是馅饼中的一个组成部分，变量是馅饼的数量。
对于整数问题，在文献中有很多近似技术，如果你可以用“接近某个界限”，例如（常使用NP-Complete或integer linear programming），或者如果你需要一个精确的解决方案，指数的解决方案可能是你最好的答案。（当然，除非local ratio technique）