最具成本效益的套餐组合(发货)

Question

对于我的运输方法，我有一个非常简单的函数来把包放在一起。基本上，每件事都完全按照它应该的方式工作。然而，在特殊的星座中，例如当数量为42个时，会收取比所需更多的成本。

变量$packages的填充方式如下：

Array
(
    [0] => Array
        (
            [name] => 18er
            [contain] => 18
            [cost] => 5
        )

    [1] => Array
        (
            [name] => 12er
            [contain] => 12
            [cost] => 5
        )

    [2] => Array
        (
            [name] => 6er
            [contain] => 6
            [cost] => 8
        )

)

我的函数的相关部分如下：

$overrun    = 42; // Items in cart
$cost       = 0;
$filled     = array();
$quantities = array();
foreach( $packages as $the_package ){
    $delivers = floor( $overrun / $the_package['contain'] );
    if( ! $delivers ) {
        continue;
    }
    $filled[$the_package['name']] = $delivers;
    $overrun = $overrun - ( $delivers * $the_package['contain'] );
    $cost = $cost + ( $delivers * $the_package['cost'] );
}

计算后，变量$filled定义如下，运费为$18：

Array
(
    [18er] => 2
    [6er] => 1
)

最优将是$15的结果，因此变量$filled必须如下所示：

Array
(
    [18er] => 1
    [12er] => 2
)

我想我根本不能使用这个简单的foreach循环。你能给我一些如何解决这个问题的帮助吗？

你可以在3v4l.org上找到一个可用的例子。

非常感谢!

Answer 1

我一半的答案来自this question and the subsequent answers，所以如果我的答案有效，请也在那里投票。在这里，我将从该代码的一个调整版本开始。它的要点是，它获取给定数组$numbers中的每一项，例如[6, 12, 18]，并查看它是否可以求和为$target，例如42。我对这个函数的调整是，我还传入了一个$final数组，这样我就可以得到一些东西，而不仅仅是打印。

function subset_sum(array &$final, array $numbers, int $target, array $partial = []): void
{
    $s = array_sum($partial);

    if ($s === $target) {
        if (!in_array($partial, $final, true)) {
            $final[] = $partial;
        }
    }

    if ($s >= $target) {
        return;
    }

    for ($i = 0; $i < count($numbers); $i++) {
        $n = $numbers[$i];
        $remaining = array_slice($numbers, $i + 1);
        subset_sum($final, $remaining, $target, array_merge($partial, [$n]));
    }
}

然而，该函数的问题在于，它尝试所提供的数组的每一种组合，但一旦使用了数字，它就不会以相同的顺序再次尝试。因此，在您的示例中，该函数永远不会尝试18 + 18 + 6，因为18不会在数组中出现两次。为了解决这个问题，我们将使用array_fill根据需要重复我们的数字。例如，我们需要6在数组中出现七次才能指向42。

function grow_initial_array(array $numbers, int $max): array
{
    $numbers = array_unique($numbers);
    $ret = [];
    foreach ($numbers as $n) {
        assert(is_int($n));
        // The maximum number of times that $n can be divided into $max
        $x = (int)floor($max / $n);
        // Fill our array with that many items (repeat 6 seven times for 42)
        $f = array_fill(1, $x, $n);
        $ret = array_merge($ret, $f);
    }

    return $ret;
}

对于[18, 12, 6]的三个输入，这将生成一个数组：

Array
(
    [0] => 18
    [1] => 18
    [2] => 12
    [3] => 12
    [4] => 12
    [5] => 6
    [6] => 6
    [7] => 6
    [8] => 6
    [9] => 6
    [10] => 6
    [11] => 6
)

接下来，我们需要将这个简单的数据与您的业务逻辑合并。有很多方法可以做到这一点，包括array_reduce等函数，但我将通过嵌套的foreach循环保持简单，这可能不是很好的性能/美观。这段代码创建了一个新数组，其中的键是包选项的总和。这些和的值是另一个可能的选项数组(只是以防两个或更多的组合加起来是相同的总数)。第三个内部数组是最初列出的产品选项数组。

function remerge_to_packages_with_sums(array $final, array $packages): array
{
    $package_options = [];
    foreach ($final as $numbers) {
        $package_option = [];
        $sum = 0;
        foreach ($numbers as $n) {
            foreach ($packages as $p) {
                if ($p['contain'] === $n) {
                    $package_option[] = $p;
                    $sum += $p['cost'];
                    break;
                }
            }
        }

        if (!array_key_exists($sum, $package_options)) {
            $package_options[$sum] = [];
        }

        $package_options[$sum][] = $package_option;

    }

    return $package_options;
}

该代码生成以下数组(只显示第一个键)：

Array
(
    [18] => Array
        (
            [0] => Array
                (
                    [0] => Array
                        (
                            [name] => 18er
                            [contain] => 18
                            [cost] => 5
                        )

                    [1] => Array
                        (
                            [name] => 18er
                            [contain] => 18
                            [cost] => 5
                        )

                    [2] => Array
                        (
                            [name] => 6er
                            [contain] => 6
                            [cost] => 8
                        )

                )

        )
        // Extra items removed for display purposes
    )
)

如果你愿意，你可以停在这里，你的答案就在深度嵌套的数组中。但如果您想继续下去，可以将其转换为一个较小的数组，其中键是总和，值是与初始输入匹配的数组的数组：

function reduce_merged_array(array $merged_array): array
{
    $final = [];
    foreach ($merged_array as $sum => $package_collection) {
        if (!array_key_exists($sum, $final)) {
            $final[$sum] = [];
        }
        foreach ($package_collection as $pc) {
            $local = [];
            foreach ($pc as $item) {
                if (!array_key_exists($item['name'], $local)) {
                    $local[$item['name']] = 0;
                }
                $local[$item['name']]++;
            }
            $final[$sum][] = $local;
        }
    }

    return $final;
}

这会产生：

Array
(
    [15] => Array
        (
            [0] => Array
                (
                    [18er] => 1
                    [12er] => 2
                )

        )

    [18] => Array
        (
            [0] => Array
                (
                    [18er] => 2
                    [6er] => 1
                )

        )
    // Only two shown for example
)

我们可以将这些函数与这段代码一起使用，代码中的注释应该能够解释一切：

// Initial array
$packages = [
    [
        'name' => '18er',
        'contain' => 18,
        'cost' => 5,
    ],
    [
        'name' => '12er',
        'contain' => 12,
        'cost' => 5,
    ],
    [
        'name' => '6er',
        'contain' => 6,
        'cost' => 8,
    ],
];

// Get just our contain values
$values = array_column($packages, 'contain');

// This is our quantity that we are targeting
$target = 42;

// Will hold the result of potential summing options
$sum_options = [];

// Duplicate our items in values so that we can get every possible combination
$value_duplicated = grow_initial_array($values, $target);

// Calculate all possible sums
subset_sum($sum_options, $value_duplicated, $target);

if (0 === count($sum_options)) {
    // TODO: Nothing found that matches
    exit;
}

// Convert back to packages
$packages_with_sums = remerge_to_packages_with_sums($sum_options, $packages);

// Convert to simplified array
$reduced = reduce_merged_array($packages_with_sums);

// Sort by sum, smallest first
ksort($reduced);

// Best options
$best_price = array_key_first($reduced);
$best_priced_options = reset($reduced);

// Worst options
$worst_price = array_key_last($reduced);
$worst_priced_options = end($reduced);

$best_priced_options和$worst_priced_options变量是数组，仅供参考，因为可能有两个或更多的组合加起来为给定的价格。