algorithm - 解决一些未知数必须为整数的方程

Question

求解S和T1…TN，使下列总和最小化：
∑nk=1（1-分钟（s·tk，ck）/最大（s·tk，ck）），
在哪里？
C1…CN>1，
S>0，
T1…tn∈_+
编辑以澄清问题描述：
“你需要多快的算法。”不是超快的（但不是多秒）。n大约在5-10左右。
至于实际问题，我在“页面”上有不同大小的“元素”，这个页面需要转换成一个X元素的最大基数格式，元素的基本大小必须是整数。但是，在新格式中，任何元素都可以通过为页面设置的单个缩放因子进行缩放。
所以c1…cn是原始页面上元素的大小。T1…TN是新页面格式中的新整数大小。（T1…TN需要小于X。）新页面格式的缩放因子为S。
更多
就我之前所做的，我发现了原始页面上最大的元素，如果它比X小，我只在新页面上使用现有元素大小，而将每个元素大小整为整数。但是，如果原始页上最大的元素大于x，我将其大小除以x，得到新页的缩放因子s，将c1…cn除以s，得到t1…tn。但这会导致新页上每个元素的大小差异平均约为1-3%，但最大的元素除外。不是很明显，但我是个完美主义者。

Answer 1

您还应该阅读integer unknowns的线性规划。
即使这不是线性规划，它可能会给你一个什么样的想法寻找。
另外，您可能会转到https://mathoverflow.net/以获得重新建模问题的帮助（您有一个整数域上的优化问题，目标函数中存在不连续性，而我的数学对正确地放置它有点生疏；也可以检查combinatorial optimization）
（对于正确的解决方案，请跳到下面的edit4）
编辑：
关于线性
寻找最大值
∑nk=1（1-分钟（s·tk，ck）/最大（s·tk，ck））
可能和看最大值一样
∑nk=1（最大（s·tk，ck）-最小（s·tk，ck））
前提是
σnk=1 max（s·tk，ck）>0
（哪个总是？真的吗？考虑到你的条件）
和期限
∑nk=1（最大（s·tk，ck）-最小（s·tk，ck））
可以写成
∑nk=1 abs（s·tk-ck）
如果上面的问号表示
S和TK最大化
最小化所有CK
所以所有c=1，以及所有t和s································
好吧，原来我的建议是错的，因为我假设一个问题不会变成一个案例，事实上很明显是这样。
编辑2：
我的数学是生疏的，上面的过程是不正确的（第一步），但是结论/解决方案似乎是有效的，所以我不会更正（它变得有点复杂）
edit3（ck是常数和其他修正）：
也许我应该整理一下答案，我相信下面的推理就足够了：
ck是常数而不等于1这一事实无关紧要。最大化原创表达
∑nk=1（1-分钟（s·tk，ck）/最大（s·tk，ck））
你应该尽量减少
∑nk=1分钟（s·tk，ck）/max（s·tk，ck）
因为所有的领域都是正的，使这个比率最小，你必须使分子尽可能小，分母尽可能大。
如果
tk为0（对于所有k）；？min（0，ck）/max（0，ck）=0/ck=0
如果
s接近于零（与上面类似，只有它是等于0的极限）
s接近无穷大–“min（∞，ck）/max（∞，ck）=ck/∞=0
（上述等式应使用极限符号…）
所有k的tk接近无穷大
（每一个条件本身就足够了，代表了解决方案，当组合它们时，不要让s接近0，而tk接近无穷大，反之亦然；在这种情况下，哪一个接近得更快是很重要的）
edit4:（实际解决方案）
基本上所有上面都给出了一个错误的答案，因为我在寻找原始目标函数的最大值，而不是最小值。
至于最小值，它有点有趣，如果每个项都达到最小值
最小（s·tk，ck）/最大（s·tk，ck）=1
这是给定参数域的这个术语的最大值。如果我们假设ck是整数，那么可以找到
S=1
TK=CK
但是在一般情况下，ck不是整数，所以我们需要找到ck/s是整数的s。
如果我们能把ck写成
nk/dk，其中n，d∈+（换言之，如果ckdegenerate）
那么一个解决方案可以是
s=1/∏nk=1dk
tk=nk/dk·∏nk=1dk
（即∈_+）
笔记
与其选择s是所有分母的乘积，不如将它设置为最大公分母，然后可以适当地计算tk。
注2：
绘制相关函数的图表有助于我发现错误的理解问题（意识到最小值更有趣）。我也意识到这些函数是连续的（但不是光滑的，所以推导是不连续的）。
注3：
上述解适用于有理数，但我认为无理数不会使解无用，因为无理数的十进制或其他有理表示将给出接近于实解的近似解，因为表示接近无理数的实际值。