如何最小化两个整数，使它们的乘积小于某个值？

Question

给定两个整数，我如何最小化它们以使它们的乘积小于其他值，同时保持它们的相对比？

这是形式问题。实际问题是这样的：我有 width/height 个包含随机值的像素分辨率（任意维度从 1 到 8192）。我想调整值对，使它们的乘积不超过某个像素总数（例如：1000000），并且我需要确保调整后分辨率的纵横比保持不变（例如：1.7777）。

天真的方法是运行一个循环，每次从宽度中减去 1，调整高度以匹配纵横比，直到它们的乘积低于阈值。例如：

int wid = 1920;
int hei = 1080;
float aspect = wid / (float)hei;
int maxPixels = 1000000;
while (wid * hei > maxPixels)
{
    wid -= 1;
    hei = wid / aspect;
}

当然必须有更多的分析方法来解决这个问题？

Answer 1

编辑：误读了原问题。

另一种表达问题的方式是 W 和 H 最大的 a 和 b 是什么 a/b = W/H 和 a*b < C 其中 C 是您对 .

的限制

为此，找到 D = gcd(W,H) 或 W 和 H 的最大公约数。最大公分母通常使用欧几里德算法找到。

设置x = W/D和y = H/D，这是具有相同比率的最小解。

为了在 C 下产生最大值，从 F*x*F*y <= C 的不等式开始，其中 F 将是 x 和 y

的比例因子

代数：

F^2 <= C/(x*y)

F <= sqrt(C/(x*y))

由于我们希望F是一个整数并且严格小于上面的数，

F = floor(sqrt(C/(x*y)))

这将为您提供一个新的解决方案 A = x*F and B = y*F where A*B < C and A/B = W/H.

Answer 2

，但这里是代码形式的解释：

#include <utility>
#include <numeric>
#include <cmath>
#include <iostream>

// Mathsy stuff

std::pair<uint64_t, uint64_t> ReduceRatio(const uint64_t W, const uint64_t H)
{
    const double D = std::gcd(W, H);
    return {W/D, H/D};
}

std::pair<uint64_t, uint64_t> Maximise(const uint64_t C, const uint64_t W, const uint64_t H)
{
    const auto [x, y] = ReduceRatio(W, H);
    const uint64_t F = std::floor(std::sqrt(C/double(x*y)));

    const uint64_t A = x*F;
    const uint64_t B = y*F;

    return {A, B};
}


// Test harness

void Test(const uint64_t MaxProduct, const uint64_t W, const uint64_t H)
{
    const auto [NewW, NewH] = Maximise(MaxProduct, W, H);

    std::cout << W << "\u00D7" << H << " (" << (W*H) << " pixels)";

    if (NewW > W)
        std::cout << '\n';
    else
        std::cout << " => " << NewW << "\u00D7" << NewH << " (" << (NewW * NewH) << " pixels)\n";
}

int main()
{
    Test(100000, 1024, 768);
    Test(100000, 1920, 1080);
    Test(500000, 1920, 1080);
    Test(1000000, 1920, 1080);
    Test(2000000, 1920, 1080);
    Test(4000000, 1920, 1080);
}

// g++ -std=c++17 -O2 -Wall -pedantic -pthread main.cpp && ./a.out
// 1024×768 (786432 pixels) => 364×273 (99372 pixels)
// 1920×1080 (2073600 pixels) => 416×234 (97344 pixels)
// 1920×1080 (2073600 pixels) => 928×522 (484416 pixels)
// 1920×1080 (2073600 pixels) => 1328×747 (992016 pixels)
// 1920×1080 (2073600 pixels) => 1872×1053 (1971216 pixels)
// 1920×1080 (2073600 pixels)

如何最小化两个整数，使它们的乘积小于某个值？

How can I minimize two integers so that their product is less than a certain value?

resolution

pixel

square