3

我目前正在为日本送货上门公司Kuroneko开发一个载体模块。该承运人连同重量一起考虑了箱子的大小。但它不使用音量，那太容易了。它使用三个维度（高度、重量和深度）的总和。

如果您只有一种产品要装箱，这仍然很容易，但是当您需要装箱 2 种产品时会发生什么？假设您有两个尺寸为 (x1,y1,z1) 和 (x2,y2,z2) 的乘积，您如何以使 X+Y+Z 最小的方式计算最终的盒子尺寸 X,Y,Z？

这是我的临时解决方案，但请告诉我是否有更好的计算方法：让 m1 成为第一个产品的最小尺寸，min(x1,y1,z1) 和第二个产品的最小尺寸。您必须考虑盒子中产品的旋转以最佳方式适合它们，从而为两种产品定义新尺寸 nx,ny,nz。假设 nx = m。如果 m = x 则 ny = y，nz = z，否则如果 m=y，则 ny= x，nz = z，否则如果 m=z，ny = y，nz= x。因此，总框大小变为 2*nx,max(ny1,ny2),max(nz1,nz2)。

但据我所知，我认为这种方法不适用于 2 种以上的产品。任何想法？

4

4 回答 4

8
  • 在这里回答演示。
  • 您可以在此处查看代码（我添加了画布以进行可视化）

逻辑：

  1. 查找总体积 (w*h*d)[+(w*h*d)..]

  2. 收集所有可能的宽度高度和深度值，从最低到最高排序

  3. 找到所有可能的宽度和排列，然后是高度，然后是宽度

    3a。示例：宽度范围 1、2、3 的和排列将是 1、2、3、4、5、6

    3b。我们需要这个，因为根据示例 (3a.)，宽度的最终值绝不可能是 1.5。

  4. 根据 (3.) 计算的排列，找到宽度、高度和深度的所有可能组合

  5. 存储总交易量等于或大于来自 (1.) 的总交易量的所有组合

    5a。这是因为最终成交量不可能小于实际成交量 (1.)

    5b。对于大于 (1.) 的卷，这意味着这是死空间。

  6. 从 (5.) 升序对所有组合进行排序，第一个结果将是最准确的 Volume

  7. 最准确的体积仍然可能具有不同的尺寸

    7a。示例：第 16 卷可以是 2x2x4 或 4x4x1 或 2x1x8 或 16x1x1

    7b。找到每个的 W+H+D 的总和，最小的总和将是更准确的尺寸。

    7c。(7a.) 2+2+4 = 8, 4+4+1 = 9, 2+1+8 = 11, 16+1+1 = 18 .... 所以我们的脚本会选择 2 x 2 x 4

于 2014-02-14T09:54:22.550 回答
3

我一直在寻找这种算法，但链接已关闭，但是我可以使用回程机器找到它。

无论如何，我会在这里发布它，因为它可能对其他人有用

<?php

$test = '1,2,3|4,2,1|0.1,0.9,0.01';

$dimensions = explode("|", $test);

//1. Find total volume
$volume = 0;
//2. Find WHD ranges
$widthRange     = array();
$heightRange    = array();
$depthRange     = array();
foreach($dimensions as $dimension) {
    list($width, $height, $depth) = explode(',', $dimension);

    $volume += $width * $height * $depth;

    $widthRange[] = $width;

    $heightRange[] = $height;

    $depthRange[] = $depth;
}

//3. Order the WHD ranges
sort($widthRange);
sort($heightRange);
sort($depthRange);

echo 'Volume: '.$volume.'<br />';
echo 'Width Range: '.implode(', ', $widthRange).'<br />';
echo 'Height Range: '.implode(', ', $heightRange).'<br />';
echo 'Depth Range: '.implode(', ', $depthRange).'<br />';

//4. Figure out every combination with WHD
$widthCombination   = array();
$heightCombination  = array();
$depthCombination   = array();

function combination($list) {
    $combination = array();
    $total = pow(2, count($list)); 
    for ($i = 0; $i < $total; $i++) {   
        $set = array();
        //For each combination check if each bit is set  
        for ($j = 0; $j < $total; $j++) {  
           //Is bit $j set in $i?  
            if (pow(2, $j) & $i) $set[] = $list[$j];       
        }  

        if(empty($set) || in_array(array_sum($set), $combination)) {
            continue;
        }

        $combination[] = array_sum($set);
    }

    sort($combination);

    return $combination;
}

$widthCombination = combination($widthRange);
$heightCombination = combination($heightRange);
$depthCombination = combination($depthRange);

echo 'Width Combination: '.implode(', ', $widthCombination).'<br />';
echo 'Height Combination: '.implode(', ', $heightCombination).'<br />';
echo 'Depth Combination: '.implode(', ', $depthCombination).'<br />';

$stacks = array();
foreach($widthCombination as $width) {
    foreach($heightCombination as $height) {
        foreach($depthCombination as $depth) {
            $v = $width*$height*$depth;
            if($v >= $volume) {
                $stacks[$v][$width+$height+$depth] = array($width, $height, $depth);
            }
        }
    }
}

ksort($stacks);

foreach($stacks as $i => $dims) {
    ksort($stacks[$i]);
    foreach($stacks[$i] as $j => $stack) {
        rsort($stack);
        break;
    }

    break;
}

echo '<pre>'.print_r($stacks, true).'</pre>';

所有的功劳都属于克里斯蒂安·布兰克拉

于 2018-03-14T01:25:37.217 回答
0

用python实现了算法，Macr1408翻译了代码，感谢算法的原作者Christian Blanquera。

from functools import reduce
from itertools import product

def combination(dim: list) -> list:
    """Calculate all possible sum permutations for a given list
    of numbers.

    Args:
        dim (list): A list of numbers

    Returns:
        list: All possible sum permutations
    """
    combination = []
    total = pow(2, len(dim))
    for i in range(total):
        set_v = []
        for j in range(total):
            if (pow(2, j) & i):
                set_v.append(dim[j])
        
        if len(set_v) == 0 or sum(set_v) in combination:
            continue

        combination.append(sum(set_v))
    return sorted(combination)

# dimensions => [(w1, h1, l1), (w2, h2, l2), ...]
def calculate_volumetric_total(dimensions: list[tuple[float, float, float]]) -> tuple:
    """Calculate the volumetric dimensions of the box needed to store products
    with sizes stored as tuples of (width, height, length). Based on the following
    algorithm:

    1. Find total Volume (w*h*d)[+(w*h*d)..]
    2. Collect all possible width height and depth values, sort each from lowest to highest
    3. Find all possible sum permutations for width, then for height, then for width
        3a. Example: sum permutations for width ranges 1,2,3 would be 1, 2, 3, 4, 5, 6
        3b. we need this because in no way could the final value for width be 1.5 for example based on the example (3a.)
    4. Find all possible combinations of Width, Height and Depth based on the permutations calculated on (3.)
    5. Store all combinations where the total volume is equal or greater than the total Volume from (1.)
        5a. This is because it is not possible that the final volume could be less than the actual Volume (1.)
        5b. For Volumes greater than (1.) it means that's dead space.
    6. Sort all combinations from (5.) Ascending, the first result will be the most accurate Volume
    7. It is possible that the most accurate volume still could have different dimensions
        7a. Example: Volume 16 can be 2x2x4 or 4x4x1 or 2x1x8 or 16x1x1
        7b. Find the sum of W+H+D for each and the smallest sum would be the even more accurate dimensions.
        7c. Example from (7a.) 2+2+4 = 8, 4+4+1 = 9, 2+1+8 = 11, 16+1+1 = 18 .... So our script would choose 2 x 2 x 4

    Args:
        dimensions (list[tuple[float, float, float]]): A list of all products/boxes
        to store together in the form width, height, length.

    Returns:
        tuple: A tuple of width, height, length values representing the box needed to
        store all the provided dimensions in.
    """
    # 1
    total_volume = sum([reduce(lambda x, y: x*y, t) for t in dimensions])
    
    # 2, sorting happens when combining values
    all_widths = [t[0] for t in dimensions]
    all_heights = [t[1] for t in dimensions]
    all_lengths = [t[2] for t in dimensions]

    # 3
    width_combination = combination(all_widths)
    height_combination = combination(all_heights)
    length_combination = combination(all_lengths)

    # 4
    vals = {}
    for perm in product(width_combination, height_combination, length_combination):
        # 5
        volume = reduce(lambda x, y: x*y, perm)
        if volume >= total_volume:
            vals[sum(perm)] = perm
    
    # 6
    return vals[sorted(vals.keys())[0]]
于 2021-12-20T17:50:45.903 回答
0

上述算法不适用于维度： $test = '100,10,10|50,50,50'; 第一个结果是：

(
  [0] => 50
  [1] => 60
  [2] => 50              
)

但第一个产品不适合。组合数组应仅包含大于或等于最大维度大小的大小总和（宽度组合不应包含 50）。

于 2019-06-26T11:56:47.977 回答