算法：找到两个差最小且乘积已知的正整数

Question

一些背景...

我目前正在构建一个宏来估算注塑成型工具的成本。这些工具具有充满塑料的空腔。一个工具的型腔数量就是将要成型的零件数量。

到目前为止，我的程序将根据客户需求确定工具可以具有的最小型腔数。这个数字总是偶数。该工具应具有偶数个型腔。给定空腔的边界长度和宽度，并设置空腔在工具内可以占据多少 space 的限制，我需要我的程序来计算沿长度和宽度的空腔数量的组合，其差值为最小化，其乘积等于工具应具有的最小型腔总数。

我正在编程我的宏是 SolidWorks VBA。我首先在 Excel 构建了这个问题并使用了求解器工具。但是，我无法找到一种方法来引用 SolidWorks 中的 Excel Solver Tool 来自动执行此优化问题。我希望找到一组巧妙的方程式来为我解决这个特定问题。但是，如果其他人对使用什么有更好的想法，那就太棒了。

正在以优化格式改写...

变量

x = 沿工具宽度的空腔数量
y = 沿工具长度的空腔数量
z = 建议的总型腔数

Objective函数

最小化 x - y

这样

x * y = z
x >= 1
y >= 1
x <= y
x 是一个整数
y 是一个整数

例子

我的宏说为了满足需求，我们的工具需要至少有 48 个型腔。找到沿工具长度和宽度的空腔数量，使差异最小化，乘积等于 48。理想情况下，宏将 return x = 6 和 y = 8。

谢谢！

Answer 1

澄清一下，在这个问题中，您实际上是指 Min y-x 而不是 Min x-y？否则会有一个天真的解决方案采用 x = 1 和 y = z。 Min x - y = 1-z.

我不会在 VBA 中编程，但这是我的想法。

因为x和y是正整数并且乘积是z，所以x <= y。您基本上可以从 x = floor(sqrt(z)) 开始并递减直到 x = 1.

对于每个 x，检查是否存在满足 x * y = z 的整数 y。如果有，打破循环，这就是你要找的那对。否则继续直到 x = 1

如果您需要任何伪代码，可以将其翻译成VBA。在这里

int x, y;
for (x = floor(sqrt(z)); x >= 1; --x)
{
    y = z / x;
    if (x * y == z)
        break;
}

Answer 2

我想你可以测试几个例子。不需要花哨的算法。

如果放宽条件为x和y2个数，其乘积为z且差值最小，则答案为SQRT(z) .

这不是满足您需求的整数（一般情况下）。但是，您可以尝试在平方根周围取整数，看看它们是否能整除 z。您命中的第一个（即与 SQRT(z) 的最小差异）应该具有最小差异。

如果放宽条件使|z - x * y|最小化，那么我建议测试sqrt(z)附近的数字。您需要检查两种情况——平方根的下限和上限（以及其他适当的数字）。

Answer 3

以防万一将来有人需要类似的东西，但无法弄清楚伪代码，我就把它写下来了。我不确定如何将它输出为两个值，所以我只是将它们作为一个字符串放在一起供用户查看。

Option Explicit
Function Factors(ByVal Test As Long) As String
    Dim Val As Long
    Dim i As Long
    Val = Test

    i = Int(Sqr(Val))
    While Val / i >= 2
        If Int(Val / i) * i = Val Then
            Factors = i & " & " & Val / i
            Exit Function
        End If
    i = i - 1
    Wend
End Function

算法：找到两个差最小且乘积已知的正整数

Algorithm: find two positive integers whose difference is minimized and whose product is known

excel

vba

algorithm

optimization

solidworks

一些背景...

正在以优化格式改写...

变量

Objective函数

这样

例子