PHP - 困难的数学计算

Question

项目描述

该项目计算马需要摄入多少食物，这基于许多变量。用户输入有关每匹马和首选饲料的信息。每种饲料都有多种类型的维生素和营养物质。

1匹马使用多种类型的饲料。

我们拥有什么

我们拥有特定马匹所需每种营养素的最小和最大值。

我们拥有一个或多个不同类型的饲料的内容，每种饲料可能有大约20-30种不同的营养素和维生素。我们还拥有价格，并希望使用它来节省资金。

（每次只针对一匹马进行计算）

示例

我们使用A、B和C表示营养素。

马需要：（A，B，C）MIN（30，7，9）MAX（35，9，17）

饲料1包含：（A，B，C）VALUES（16，2，3）
饲料2包含：（A，B，C）VALUES（0，4，9）

一个工作解决方案是2*Feed1和1*Feed2。

问题

我希望系统根据每种营养素的最小/最大值计算出完美平衡，并仍然保持价格尽可能低。

工作方案

如果我首先计算每种饲料的最大可能数量，将可以随机化直到看起来可行。然后用户将能够更改数量，如果它不完美。

<?php
function randomizerLoop(){
    foreach($feeds as $feed){
        $max['A'] = floor($horse_max['A']/$feed['A']);
        $max['B'] = floor($horse_max['B']/$feed['B']);
        $max['C'] = floor($horse_max['C']/$feed['C']);
        $maxRand = MIN($max['A'], $max['B'], $max['C']);

        $amounts[$feed['id']] = rand(0, $maxRand);
    }

    return $amounts;
}
?>

这段代码会一直尝试直到获得有效的余额，而不是使用某些酷炫的计算方法来在第一次尝试中找到余额。

我只需要一个解决方案的思路，但不想使用rand()。

更多信息

每个用户都可以添加无数匹马，但一次只能为一匹马计算（目前为止）。

还将有可能添加无数饲料（由用户定义），每种饲料可能有 20-30 个变量。根据解决方案，这可能需要对每个自动计算的饲料数量进行限制。

如果我们使用20种不同的饲料，每种饲料有 20-30 个变量，同时又以 整数 而非 布尔值 来定义数量，那么就会有很多组合。

- SebHallin

---

时间要求和马的数量怎么样？您是否只关心准确性，还是速度也是一个问题？ - varocarbas

[...]和优选饲料 您是否想要将优选饲料纳入考虑范围，或者只希望以最便宜的价格获取饲料？此外，如果不匹配，它应该怎么办？这意味着如果您购买饲料，您会有营养过剩或不足的问题。 - Rizier123

@varocarbas 精度和速度都很重要，但如果我只看到一些解决方案，我可以进一步为系统进行优化。 - SebHallin

@Rizier123 在自动计算中，价格应该是优先考虑的（按内容每价）。您可以假设它总是以某种方式匹配，并且我稍后会进行调整。 - SebHallin

Answer 1

这是一个线性规划问题。

     MIN     MAX
A    30      35
B    7       9
C    9       17

          A    B    C
Feed1     16   2    3
Feed2     0    4    9

让食物包含x份饲料1和y份饲料2。根据您的问题：

30<16*x+0*y<35
=> 30<16x<35

使用ceil()函数将30除以16，得到x（即2）。接下来，您有3<4y<5，同样使用ceil()，您将得到y=1。

现在考虑您的项目，

对于大量的提要，计算这么多方程式将会很困难。

我们应该使用矩阵进行简化。上述方程的矩阵如下：

  A   *  B   =   C
|16 0| | x |   | 30 |
|2  4| | y | = |  7 |
|3  9|         |  9 |

现在使用Lapack::pseudoInverse()来计算矩阵A的逆矩阵并将其与C相乘。 然后只需将矩阵B中x和y的值等同于答案并使用ceil()函数即可。

- Golden_flash

---

这个程序如何考虑价格因素？ - Rizier123

我认为这个紫色数学示例更好地解释了它。成本方程是C = 方程式。然而，在编程方面组合变量似乎很困难。 - Chizzle

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Golden_flash

OP确实提到了价格：“我们也有价格，并希望利用它来节省资金。” 因此，整个问题是找到适合马匹需求的营养物质，并以最低价格购买...而不仅仅是购买最少总饲料量，我认为您的方法正在这样做。 - Chizzle

线性规划用于最小化或最大化一个值。由于 OP 没有说明这些值可以是有理数或整数，因此该方法找到了最小化成本的整数值。如果要使用有理数，则不要使用 ceil 函数，您将得到 x 和 y 的 p/q 表示。然后测试用例的答案将为 x=1.85 和 y=0.8125。 - Golden_flash

Answer 2

您想做的是尝试每种饲料的每种组合。假设有5种类型的饲料。您已经知道如何计算每种饲料类型的最大值。因此，我认为您已经有了类似以下内容的东西：

$feeds_cost = array of costs for each feed
$feeds_ingredient_A = array of how much ingredient A each feed has
$feeds_ingredient_B = array of how much ingredient B each feed has
$feeds_ingredient_C = array of how much ingredient C each feed has
$feeds_max = array of maximum quantity of each feed allowed

现在，对于这5种类型，您想尝试的量是{0,0,0,0,0}，{0,0,0,0,1}，{0,0,0,0,2} ... {$feeds_max [0]，$feeds_max [1]，$feeds_max [2]，$feeds_max [3]，$feeds_max [4]}。对于每个数量集，您需要执行以下操作：1.确保数量满足最低要求。 2.如果满足最低要求，则计算成本。

所以，此时，您已经得到了符合最低要求但不超过最大要求的每个数量的成本。您不需要存储所有内容。维护两个变量：$best_quantities（每种饲料的计数数组）和$best_cost。如果某个数量使用更便宜的成本满足要求，则替换$best_quantities和$best_cost。

除了遍历所有数量之外，一切都很简单。这并不是非常困难。您维护您正在递增的索引。最初，它为零，但它会上升到最高饲料索引（如果您有5种饲料，则为4）。增量函数如下：

function increment_counts($feeds_max, $quantities, $index)
{
    if($index>sizeof($quantities)) return null;
    $quantities[$index]++;
    if($quantities[$index] > $feeds_max[$index])
    {
        $quantities[$index]=0;
        return increment_counts($feeds_max, $quantities, $index+1);
    }
    return $quantities;
}

假设我从头部正确地键入了这段内容，它将逐个计算数量。你可以通过增加索引0并用返回值替换当前数量来不断调用它。当它返回null时，你就完成了。

我确定我至少犯了一个错误，但这是我解决这个问题的方法。

- kainaw

Answer 3

我会专注于最小值，以尽量降低成本。无论如何，建议的方法的整个重点是满足特定目标，这些目标可能像所需的那样多变（例如：强制营养素E和G至少获得MIN和MAX之间一半的值）。

基本结构由三个循环组成：一个主要循环遍历所有营养物质; 两个内部循环尝试所有可能的饲料组合。

NUTRIENT A
Trying feed1 until reaching minimum (because feed2 is zero). 
Best so far: 2*feed1=32A.

NUTRIENT B
Starting from 2*feed1=4B, +feed2 reaches minimum.
Best so far: 2*feed1+feed2=8B.

NUTRIENT C
Starting from 2*feed1+feed2=15C which is fine already.
Best so far: 2*feed1+feed2=15C.

这种方法的更高级版本是回去检查（例如，在目标从一开始就达到的情况下，如维生素C的情况下）是否可能有更好的替代方案。无论如何，这种实现的复杂性和组合数量都会明显增加。

我认为这是一种相当适应性强且准确的方法。实现基本版本的算法并不太困难（但也不是太直接；这就是我为什么没有在这里写它的原因），应该能够提供合理的准确度和速度。在测试和了解其性能后，您可以考虑进一步改进它（例如，通过重新分析某些情况或考虑非MIN目标）。

- varocarbas