ruby - Ruby 中利润的优化

Question

我正在使用 Ruby，但对于这个问题来说，这并不重要。

假设我有两种不同类型的资源，其数量用a 和b 表示。我可以分配 d 新资源，并且由于 a 和 b 的生产成本和值(value)相同，我可以选择分配资源无论哪种方式都是最有利可图的。

最好这样解释:(a + j) * (b + k) = c，其中 j + k = d。我想通过最佳资源分配来最大化 c，同时理解这两种不同类型资源的成本及其对生产的值(value)是相同的。所有变量都是正整数，a 和 b 都大于 0。这是我的天真的暴力破解方法:

def max_alloc(a, b, d)
  max_j = 0
  max_k = 0
  max_c = 0
  (0..d).each do |j|
    k = d - j
    c = (a + j) * (b + k)
    if c > max_c
      max_c = c
      max_j = j
      max_k = k
    end
  end
  [max_j, max_k]
end

我希望我缺少某种数学或算法“技巧”，这将使我不必诉诸蛮力。

Answer 1

您真的需要一种算法来做到这一点吗？这是一个简单的最大/最小优化问题。

现在考虑等式

它是j的函数, 所以我们称它为 f(j) :

您想查找j这样 c = f(j)是最大值...所以你想研究它导数的符号

现在你可以画符号表了

给你!最大为

这意味着 j, k你要找的一对是

对于这样的值，您将获得最大值 c :

---

在 ruby 中

def max_alloc(a, b, d)
    j = (-a + b + d) / 2.0
    j = j.round # round to prevent Float, explained at the end of this answer
    if j < 0
        j = 0 # prevent from negative values
    elsif j > d
        j = d # prevent from values greater than d
    end
    [j, d - j]
end

甚至更短

def max_alloc(a, b, d)
    j = ((-a + b + d) / 2.0).round
    j = [0, [j, d].min].max # make sure j is in range 0..d
    [j, d - j]
end

如果你喜欢的话，也可以单行

def max_alloc(a, b, d)
    [[0, [((-a + b + d) / 2.0).round, d].min].max, d - [0, [((-a + b + d) / 2.0).round, d].min].max]
end

---

深入了解案例j < 0和 j > d

让我们从 j 的边界开始必须满足:

所以 j*是:

现在，自 f(j)是总是向下开口的抛物线，绝对最​​大值将是它的顶点，所以，如前所述:

但是如果这个点超出给定范围 j 怎么办？ ？您必须决定是否选择 j* = 0, k* = d或 j* = d, k* = 0 .

自 f(j)严格增加 j < j*并严格减少 j > j* ，你越接近j* , 较大的将是 f(j)值(value)。

因此，如果j* > d选择j* = d , 如果 j* < 0然后选择j = 0 .

我在这里展示了一些情节，只是为了看看它的实际效果:

---

为什么 j.round ？

正如您刚刚了解到的那样f(j)是抛物线，抛物线有对称轴。如果j*是一个整数，你就完成了，否则对于什么整数值是f(j)最大化？好吧...对于最接近顶点的整数值；即 j.round .

注意:如果a, b和 d是整数，那么j*只能是整数或 xxx.5 .所以f(j) j.ceil 是一样的和 j.floor ...您选择。