查找满足特定条件的最接近整数值的算法

Question

编辑以通过添加单位 (ml) 和解释以 1/26 为单位测量湿试剂的难度来澄清应用程序。 'solution'这个词是有歧义的，因为它被用来表示化学溶液和问题的解决方案。

根据爱德华的回复添加了结果

现实世界的应用是，我试图确定最接近的 "convenient" 体积，以便在混合试剂 A 和 B 以创建最接近特定 [= 的溶液（在湿化学意义上）时使用45=]比例。让我们定义 "convenient" 可以被 5 整除。

示例

给定：

1. X = A/(A+B) * C 
2. Y = B/(A+B) * C
3. X + Y = C
4. A, B, C always positive integer

// e.g. a 500ml solution (wet chemistry sense) C with a 1:25 ratio of A and B 
A = 1
B = 25
C = 500

这给出了使用 X 和 Y 的体积来创建具有适当 A:B 比例的溶液（湿化学意义）。

X =   500/26 = ~19.23ml
Y = 12500/26 = ~480.77ml
C = 13000/26 = 500ml

这些是创建 500 毫升总体积的确切体积，但尝试以 1/26 毫升为单位测量试剂体积是一个挑战。

如何找到 X、Y 和 C 的 "convenient values"（可被 5 整除的整数）最接近 1/26 的倍数的 X、Y 和 C 的精确值？在这种情况下，我发现 X、Y、C 的最接近 "convenient" 值：

X =  20ml
Y = 500ml
C = 520ml

C 在这种情况下 (520ml) 大于所需的 500ml 体积，但物理测量 20mL 和 500mL 的体积比测量 1/26 的试剂体积更实用。多余的 20mL 被丢弃，这是使用 nice 值的代价。

结果基于爱德华的回答

A=1   B=25    C=500
X=20  Y=500  C2=520 

A=1   B=20    C=500
X=25  Y=500  C2=525 

A=1   B=100   C=500
X=5   Y=500  C2=505 

A=1   B=75    C=500
X=10  Y=750  C2=760 

A=1   B=50    C=900
X=20  Y=1000 C2=1020

Answer 1

让我们首先计算最优（浮动）A 和 B。

可以观察到最佳整数解是 {floor(A), ceiling(B)} 或 {ceiling(A), floor(B)}。所以我们简单地尝试两者并选择错误较少的答案。

Answer 2

解决此问题的一种方法是调整 C，使其吸收因子 A+B。那么 A 与 B 的比率就是精确的，并且 X、Y 和 C 都是整数。让 D = 5*(A+B)、C2 = ceiling(C/((double)D)) * D（四舍五入以便得到足够的 C）、X = C2/(A+B)*A、Y = C2/(A+B)*B。如果您想要 C 的最接近值，请改用 C2 = round(C/((double)D))*D。

如果您要混合化学品，您可能希望四舍五入而不是四舍五入到最接近的位置，这样您就足够了，剩下一点废物，这总比不够好。

Answer 3

您可以将其表述为具有 L1（绝对值）objective 函数的优化问题。（这是用大炮打蚊子，但我这样做是因为我想弄清楚 L1 优化。）我使用了 GLPK 包（开源）中的程序 glpsol。这是我的程序：

param A, integer, >= 0;
param B, integer, >= 0;
param C, integer, >= 0;
var x, integer, >= 0;
var y, integer, >= 0;
var e1x, >= 0;
var e1y, >= 0;

minimize e1 : e1x + e1y;

subject to

  c1 : (5*x - (C*A)/(A + B)) <= e1x;
  c2 : ((C*A)/(A + B) - 5*x) <= e1x;
  c3 : (5*y - (C*B)/(A + B)) <= e1y;
  c4 : ((C*B)/(A + B) - 5*y) <= e1y;

solve;

printf "x=%g, y=%g, error=%g\n", x, y, e1;

data;

param A := 1;
param B := 25;
param C := 500;

这是输出：

$ glpsol --model find_nice_integers.mod 
[... snip ...]
x=4, y=96, error=1.53846

这里有一些关于 how to handle absolute values in optimization problems 的注释。

Answer 4

因此，给你一个整数 C 以及另外两个整数 A 和 B 之间的比率 p:q（即 A/B = p/q ).

我会将您对 convenient 的定义解释为要求 X 和 Y 都是 5 的倍数，其中

X = A / (A+B) * C'
Y = B / (A+B) * C'
C' is close to C

用 p/q 替换 A/B 我们得到

X = p / (p+q) * C'
Y = q / (p+q) * C'

现在，为了使 X 和 Y 成为整数，p * C' 和 q * C' 都必须是 (p+q) 的倍数。并且由于我们可以假设 p:q 是不可约的（即 p 和 q 没有共同的倍数）这意味着 C' 必须被 p+q 整除.此外，C'/(p+q) 必须是 5 的倍数。所以，C' 必须是 5*(p+q).

的倍数

最接近C的5*(p+q)的倍数是：

C' := round(C/(5*(p+q)))*5*(p+q)

现在我们可以计算：

X := p/(p+q)*C'
Y := q/(p+q)*C'

它们确实是 5 的倍数，因为 C'/(p+q) 是。

让我们看看你的例子是如何表现的：

输入：

p = 1
q = 25
C = 500

然后

C' := round(500/5(1+25))*5*(1+25) = round(100/26)*5*26 = 4*5*26 = 520

因此

X := p/(p+q)*C' = 1/(1+25)*4*5*26 = 1/26*4*5*26 = 4*5 = 20
Y := q/(p+q)*C' = 25/(1+25)*4*5*26 = 25/26*4*5*26 = 25*4*5 = 500.

瞧！

查找满足特定条件的最接近整数值的算法

Algorithm to find closest integer values that meet certain criteria

algorithm

math

equation

formula