如何在加权列表之间准确分配数字 1-100（含）<= 100 long?

Question

我有一个物品清单，每个物品都有一个重量；

std::vector<float> weights{0.5, 2, 5};

此列表最多 100 项，至少 2 项。

我想将 1-100（含）的整数按反比例分布到此列表中，以便 最低权重获得最大范围。

这段代码让我很接近，但范围没有反转：

    #include <iostream>
#include <vector>
#include <iomanip>

void distributeNumbers(const std::vector<float>& numbers) {
    float total = 0;
    for (float num : numbers) {
        total += num;
    }

    int start = 1;
    int end = 100;
    std::cout << "Distributing numbers from 1 to 100 based on proportions:" << std::endl;

    for (int i = 0; i < numbers.size(); ++i) {
        float number = numbers[i];
        
        // Calculate the range length for this number
        double proportion = static_cast<double>(total-number) / total;
        int rangeLength = static_cast<int>(proportion * 100);

        // Ensure we don't assign a range of zero length
        if (i == numbers.size() - 1) {
            rangeLength = end - start + 1;
        }

        int currentEnd = start + rangeLength - 1;
        std::cout << number << ": " << start << "-" << currentEnd << std::endl;

        // Update the start for the next number
        start = currentEnd + 1;
    }
}

int main() {
    std::vector<float> numbers = {9, 4, 3, 11, 7, 19, 3};  // Example input: numbers = {6, 2, 2}
    
    distributeNumbers(numbers);
    return 0;
}

当我说成反比时，我的意思是：

对于输入，例如：

weights{2, 1}

输出应该类似于：

1-33
34-100

以及输入，例如：

weights{3,1}

输出将类似于：

1-25
26-100

和

weights{2,1,1}

会输出

1-25
26-63
64-100

Answer 1

由于数学似乎是问题，我将跳过 C++ 部分。

您首先将权重

w={1.0, 2.0, 0.25}

转换为逆权重

iw={1.0, 0.5, 4.0}

。拒绝任何输入 <=0.0

然后缩放逆权重，使它们加起来为 100。即

scale=100/(1.0+0.5+4.0) = 18.18181818

。

这意味着每个范围的长度现在只是

iw*scale={18, 9, 72}

（向下舍入）。您会发现这里缺少一个：1-18、19-27、28-99。在这个简单的情况下，您知道将最大范围加 1，但一般来说，您需要弄清楚您的特定用例是否对这种舍入有硬性要求。

Answer 2

逆位有点转移注意力。 解决非逆问题，然后求逆。

即，而不是解决

std::vector<float> weights{0.5, 2, 5};

编写一个算法来解决：

std::vector<float> weights{1./0.5, 1./2, 1./5};

然后修改算法以采用

weight

函数。 对于每个元素，求解

weight(elem)

。 您可以从

[](auto x){return x;}

开始进行初始测试，然后执行

[](auto x){return 1./x;}

以获得逆权重。

解决更简单的情况（简单权重）意味着您可以充分测试您的算法，而不必担心逆运算使其变得复杂。 无需变换算法的线性权重可编写、测试、打磨；然后向其中添加转换是另一个测试过程（并且您保留工作版本以进行比较）。

...

要按重量分割范围，首先将所有重量相加。 然后每个人都获得元素的

weight(elem)/total_weight

分数。

由于舍入而发生了一个棘手的部分；由于您只能将整数个元素放入每个元素的存储桶中，因此确定如何执行此操作需要一些额外的思考。

我会计算

weight(elem)/total_weight

，并将其分为整数部分和小数部分。 将整数部分相加并求出余数（满分 100）。 假设，您可能还剩下 12 个部分，因为整数部分加起来是 88。

然后对小数部分进行排序，并为 12 个最大的小数部分分配一个额外的整数部分。

这可以最大限度地减少输出范围内的线性误差。

另一种选择是最小化输出范围中的乘法误差。 在这种情况下，您将为任何非零元素权重分配至少 1 个整数部分（即，将 0.000001 舍入到 1）。 这可能会导致负的“余数”。

然后将余数或提取额外元素分配给具有最佳（或最差）比率的元素。

这里的数学比较困难，所以只需尽量减少线性误差即可。

...

因此，需要明确的是，我建议分几次完成，以保持简单。

首先，将元素映射到权重。

其次，标准化你的体重，使其总和为 100。

第三，为每个重量分配整数部分，并记录剩余的分数。

第四，找到剩余权重（在整数之后），并根据剩余大小的分数将它们分配给元素。

第五，将这些整数权重转化为范围。

您可以巧妙地“按顺序”执行此操作，但通过保持每个步骤简单，您可以测试您编写的逻辑是否正确，甚至可以编写简单的单元测试。