3

我很抱歉标题；坦率地说，我什至不知道我的问题是否与背包问题有关。正在阅读一些有关遗传算法的东西，并发现了这个“背包问题”。

我需要有人把我踢向正确的方向：

我正在为工厂开发一个 python web 应用程序。所以在工厂里，他们有一种叫做订单的东西。一个订单包含一个或多个产品。有一个不匹配的概念，它实际上是一个负数，用于表示特定产品在订单中出现的数量（数量方面）要少多少。

想象一个矩阵，其中列是产品，行是订单。假设所有订单（行）包含所有产品（列）。同样，有 8 个订单订单 1 到订单 8 和 5 个产品，产品 1 到产品 5。

假设，现在我的产品 1 有 6 个不匹配。我需要在所有 8 个订单中随机分配数字 6 。所以很明显2个订单不会有不匹配的数量。然后，产品 2 的不匹配数量为 9。我将不匹配数量尽可能平均地随机分配到 8 个订单中。这适用于每个产品。现在问题来了，虽然我正在将不匹配随机拆分到所有订单中，但我需要确保每个订单的总不匹配（即该行的含义）保持在最低限度。这意味着订单中的总不匹配数必须是尽可能低的数字。

    |-----|-----|-----|-----|-----|
    |  P1 |  P2 |  P3 |  P4 |  P5 |
    -------------------------------
O1  |  2  |  1  |  1  |  0  |  2  |  6
    -------------------------------
O2  |  1  |  2  |  1  |  1  |  1  |  6
    -------------------------------
O3  |  2  |  2  |  1  |  0  |  1  |  6
    -------------------------------
O4  |  1  |  2  |  0  |  1  |  1  |  5
    -------------------------------
       6     7     3     2     5

你明白吗？我需要用 Python 编写代码，但我不知道从哪里开始。

4

3 回答 3

2

你几乎有一个整数线性规划问题，除了你想要最小化的目标函数（行总和的最大值）不是线性的。寻找scipy解决优化问题。

该线程https://scicomp.stackexchange.com/questions/83/is-there-a-high-quality-nonlinear-programming-solver-for-python也可能有所帮助。

于 2012-07-17T14:46:51.110 回答
1

所以OP的问题有两个要求：随机和均匀。不过这有点矛盾，所以我想“真正随机”是不可能的。

这是我的尝试

使用 OP 的示例，我们有 4 个订单和 5 个产品。从第一个产品开始，我们随机拆分数字，所以每个产品至少会有 floor(6/4)=1 不匹配。然后我们将剩余的 2 个不匹配项随机放入 2 个产品中。

    |-----|
    |  P1 |
    -------
O1  |  2  | 2
    -------
O2  |  1  | 1
    -------
O3  |  2  | 2
    -------
O4  |  1  | 1
    -------
       6

接下来，我们处理第二个产品。同样，我们首先随机拆分数字，因此每个产品至少会有 floor(7/4)=1 不匹配。现在对于剩下的 3 个错配，为了使其尽可能均匀，我们首先将它们分配给 O2 和 O4，因为上次他们比其他人少 1 个错配。对于剩下的 1 个不匹配，我们再次将其随机分配给其中一个产品。

    |-----|-----|
    |  P1 |  P2 |
    -------------
O1  |  2  |  1  | 3
    -------------
O2  |  1  |  2  | 3
    -------------
O3  |  2  |  2  | 4
    -------------
O4  |  1  |  2  | 3
    -------------
       6     7

对所有产品重复此过程。

使用这种方式，你可以保证它尽可能的均匀（最大的区别是1），你也得到了一定程度的随机性

于 2012-07-17T20:26:30.323 回答
0

假设你这样做：

您有一系列物品要放入订单中，该序列由第一个产品的项目组成，然后是第二个产品的项目，等等。

您将第一个项目放入第一个订单，将第二个项目放入第二个订单，依此类推，在某个点再次环绕到第一个订单，一轮又一轮，直到您没有更多的项目。

那行得通吗？

于 2012-07-17T20:09:35.693 回答