我的发货方式有一个很简单的功能，就是把包裹放在一起。基本上所有的东西都能完全按照它应该的方式工作。然而，在特殊的星座中，例如，当数量为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.
非常感谢！我有一个非常简单的功能，让我的运输方法把包裹放在一起。
我一半的答案来自于 本题及后面的回答所以如果我的答案有效，也请在那边投票。我在这里先说说这个代码的调整版。它的要点是，它把一个给定数组中的每一个项目 $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] 这将产生一个.NET的数组。
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 变量都是数组，仅供参考，因为有可能两个或两个以上的组合加起来就是一个给定的价格。