PHP 找到最便宜的排列

Question

我有多种产品，它们都有尺寸，我需要找到满足最小尺寸要求的最便宜的配置。

例如，约翰至少需要 10 升的存储空间 - 可以多一些，但不能少一些。

有 2 升、3 升、5 升、8 升和 10 升选项(但这可以更改)。

例如，获取以下内容可能更便宜:

• 1x10L 容器或
• 2x5L 容器或
• 1x2L、1x3L 和 1x5L 或
• 4x3L(这个超过10L，但还是有可能便宜)

到目前为止，我已经尝试了最多 4 次循环(因为通常最大要求是 40 L)，但在某些情况下我内存不足，而且它似乎不是最有效的这样做的方式。

// Size is in mL

$available_containers = [
[
  'id' => 22700,
  'price' => 1190,
  'size' => 2000,
],
[
  'id' => 22701,
  'price' => 1245,
  'size' => 3000,
],
[
  'id' => 22702,
  'price' => 1415,
  'size' => 4000,
],
[
  'id' => 22715,
  'price' => 12300,
  'size' => 5000,
],
[
  'id' => 22706,
  'price' => 1740,
  'size' => 5000,
],
[
  'id' => 22703,
  'price' => 1510,
  'size' => 5000,
],
[
  'id' => 22707,
  'price' => 1790,
  'size' => 6000,
],
[
  'id' => 22704,
  'price' => 1770,
  'size' => 6000,
],
[
  'id' => 22708,
  'price' => 2215,
  'size' => 7000,
],
[
  'id' => 22705,
  'price' => 2195,
  'size' => 8200,
],
[
  'id' => 22709,
  'price' => 2660,
  'size' => 8200,
],
[
  'id' => 22710,
  'price' => 2799,
  'size' => 10000,
],
[
  'id' => 22711,
  'price' => 2910,
  'size' => 12500,
],
[
  'id' => 22712,
  'price' => 3260,
  'size' => 15000,
],
[
  'id' => 22713,
  'price' => 4130,
  'size' => 20000,
],
[
  'id' => 22714,
  'price' => 3770,
  'size' => 27000,
]
];

$required_size = 8; // Can change.
$container_install = 5;

foreach ( $available_containers as $v ){
  foreach ( $available_containers as $v2 ){
    foreach ($available_containers as $v3 ) {
      foreach ( $available_containers as $v4 ){

        $all_configs = [
          [
            'size' => $v['size'],
            'configuration' => [ $v['size'] ],
            'price' => $v['price'],
          ],
          [
            'size' => $v['size'] + $v2['size'],
            'configuration' => [ $v['size'], $v2['size'] ],
            'price' => $v['price'] + $v2['price'] + $container_install,
          ],
          [
            'size' => $v['size'] + $v2['size'] + $v3['size'],
            'configuration' => [ $v['size'], $v2['size'], $v3['size'] ],
            'price' => $v['price'] + $v2['price'] + $v3['price'] + $container_install + $container_install,
          ],
          [
            'size' => $v['size'] + $v2['size'] + $v3['size'] + $v4['size'],
            'configuration' => [ $v['size'], $v2['size'], $v3['size'], $v4['size'] ],
            'price' => $v['price'] + $v2['price'] + $v3['price'] + $v4['price'] + $container_install + $container_install + $container_install,
          ],
        ];


        foreach ( $all_configs as $c ){
          if ( $c['size'] >= $required_size ){
            $configuration[] = array(
              'configuration' => $c['configuration'],
              'size' => $c['size'],
              'price' => $c['price'],
            );
          }
        }
      }
    }
  }
}


// Sort by price.
$sorted_configs = array_sort($configuration, 'price', SORT_ASC); // This function simply sorts all permutations by price

Answer 1

好吧，有一些要点可以使这些循环轻量化。这个问题必须用分而治之的方法来解决。

1. 创建一个子数组，因为不需要整个数组，只需要一个从 1L 到 10L 的新子数组。
2. 子数组应按价格从低到高排序。
3. 当且仅当第一个索引中代表的最低价格只能购买一次时，打破循环。
4. 否则，您应该有一个列表，在您已经循环时获取输出。