algorithm - prestashopのキャリアモジュールの複数の製品のボックスのサイズを計算する

Question

現在、日本の宅配会社であるクロネコ向けのキャリアモジュールを開発中です。このキャリアは、重量とともに、ボックスのサイズを考慮に入れています。しかし、それはボリュームを使用しません、それはあまりにも簡単でしょう。3次元（高さ、重さ、奥行き）の合計を使用します。

箱に入れる製品が1つしかない場合でも簡単ですが、2つの製品を箱に入れる必要がある場合はどうなりますか？次元（x1、y1、z1）と（x2、y2、z2）の2つの積があるとしましょう。X+ Y + Zを最小に保つ方法で、最終的なボックスサイズX、Y、Zをどのように計算しますか？

これが私の暫定的な解決策ですが、計算するためのより良い方法があるかどうか教えてください。m1を最初の積の最小次元、min（x1、y1、z1）およびm2を2番目の積とします。ボックス内の製品の回転を考慮して、それらを最適な方法で適合させ、両方の製品の新しい寸法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つ以上の製品では機能しないと思います。何か案が？

Answer 1

• ここでデモに答えます。
• ここでコードを確認できます（視覚化するためにキャンバスを追加しました）

論理：

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.）からすべての組み合わせを並べ替えます。昇順で、最初の結果が最も正確なボリュームになります。

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 x2xを選択します。 4

Answer 2

このアルゴリズムを探していましたが、リンクがダウンしていますが、ウェイバックマシンを使用して見つけることができました。

とにかく、他の人に役立つかもしれないので、ここに投稿します

<?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>';

すべてのクレジットはChristianBlanqueraに帰属します

Answer 3

上記のアルゴリズムはディメンションでは機能しません。 最初の$test = '100,10,10|50,50,50'; 結果は次のとおりです。

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

しかし、最初の製品は適合しません。組み合わせ配列には、最大次元のサイズ以上のサイズの合計のみを含める必要があります（幅の組み合わせには50を含めないでください）。

Answer 4

アルゴリズムをPythonで実装し、Macr1408によってコードを翻訳しました。これは、アルゴリズムの元の作成者であるChristianBlanqueraの功績によるものです。

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]]