如何创建将继续运行算法直到在 Java 中成功的算法

Question

我有一个包裹 (https://github.com/skjolber/3d-bin-container-packing/)，可以帮我将物品打包到一个容器中。但是，如果物品太多，例如数量为 1000 件衬衫，而我们拥有的最大容器只能容纳 500 件，它不会尝试打包剩余的 500 件结果只是 returns null 并且不会尝试组合可用的容器。

我正在处理装箱问题。请注意，这不需要是一个精确的解决方案，因为我们只是将运费成本计算器放在一起。我偶然发现了一个可以解决大部分问题的软件包。基本上我有 5 个可用的容器。 API 收到产品请求，我收集尺寸并打包。我最初的想法是检查打包是否成功，如果成功，则将其添加到 List packingResults 对象中，这样我就有了一个列表。但是这个包的设置方式我怀疑它不会在不失去产品完整性的情况下工作。

这里是服务构造函数

public PackingService(List<Product> products) 
{
    containers = SetContainers();
    this.packer = new LargestAreaFitFirstPackager(containers);
    this.products = products;
    PrepareProductsToPack(products);
}

实际的打包方法

public List<Container> PackItems()
{
    packedResultContainers = new ArrayList<Container>();
    Container results =  packer.pack(productsToPack);
    return this.packedResultContainers;
}

最后，这是我的产品实体列表，并为打包算法准备它们。

    productsToPack = new ArrayList<BoxItem>();
    for(Product product : products)
    {
        for(int i = 1; i < product.getQuantity(); i++)
        {
            productsToPack.add(new BoxItem(new Box(product.getSku(),
                                                    product.getProductDimensions().getRoundedWidth(),
                                                    product.getProductDimensions().getRoundedDepth(),
                                                    product.getProductDimensions().getRoundedHeight(),
                                                    product.getProductDimensions().getRoundedWeight())));
        }
    }

我感到困惑的原因是因为如果初始请求无法打包，那么我需要根据有多少项将我的列表拆分为 ,2,3,4 并且没有办法我想知道我需要多少列表。

任何人都可以提供一些关于如何调整我的算法来处理这个问题的见解吗？

我还应该说明，我这样做的原因是，一旦我有了结果列表，我就会向 UPS Api 请求收集运输方式及其费率。

我正在为未来的用户更新我的答案，这就是我解决装箱问题的方法

public ArrayList<Container> PackItems()
{
    this.packingResults = new ArrayList<Container>();
    productSetsToPack = chopped(productsToPack, getInitBoxCount(productsToPack));
    int hashMapId = 0;
    for(int i = productSetsToPack.size()-1; i >= 0; i--)
    {
        ArrayList<BoxItem> itemsToPack = productSetsToPack.get(i);
        productSetsMap.put(hashMapId, itemsToPack);
        pack(itemsToPack, hashMapId, 5); //pack largest sized boxs
        ++hashMapId;
    }; 

    for (Map.Entry<Integer, Container> entry : packedContainerMap.entrySet()) {
        int containerKey = entry.getKey();
        Container packedContainer = entry.getValue();
        int smallestBoxSize = getSmallestBox(productSetsMap.get(containerKey), Integer.parseInt(packedContainer.getName()));
        packingResults.add(pack(productSetsMap.get(containerKey), smallestBoxSize));
        // ...
    }
    return packingResults;
}

Answer 1

看看 Spring 重试是否有用。在你怀疑你不会得到你的第一个列表等的方法中有重试和不同的逻辑。

Answer 2

您可以生成项目集合的所有可能子集，然后按排序顺序（从最大和递减的大小开始）迭代这些子集，直到成功。

这当然不会很好地扩展。我还使用列表索引而不是引用生成子集（将所有项目添加到列表中，创建一组从 0 到 list.size() 的数字，然后生成该集合的所有子集。）

Answer 3

嘘，你想要的是很有可能的。这将是一项艰巨的任务，尤其是当您有 5 种不同的包装尺寸时。我建议使用递归。

创建一个方法来查找您的订单可以放入的最大包裹中的最少数量。可以说它适合 4 个大盒子。然后拿起每个大箱子并尝试将其装入较小的箱子中。运行s 看起来像方框 5 是最大的方框，方框 1 是最小的方框。

box5 - box5 - box5- box5
box5 - box5 - box5- box4
box5 - box5 - box5- box3
box5 - box5 - box5- box2
box5 - box5 - box5- box1

运行可以装进 3 个大箱子和 1 个小箱子。

找到最大盒子的代码可能是这样的 while 循环

int boxCount = getInitBoxCount(products);

public int getInitBoxCount(ArrayList<BoxItems> items)
{
    if(productsFit(products,sizeLarge) == null)
    {
        ArrayList<BoxItems> temp1 = new ArrayList<BoxItems>();
        ArrayList<BoxItems> temp2 = new ArrayList<BoxItems>();

        for(int x = 0; x < items.length ; x++)
        {
           if(x > items.length/2)
           {
               temp1.add(items.get(x)) 
           }
           else
           {
               temp2.add(items.get(x))
           }
        }
        return getInitBoxCount(temp1) + getInitBoxCount(temp2);
    }
    return 1;
}

这会不断地将您的 BoxItems 列表分成两半，直到它适合盒子的数量

所以现在我们已经确定了可行的运输安排，但也可能有很多额外的 space。

接下来的 2 个步骤将是创建一个递归的方法来 trim 减小框的大小，例如

// 5 is the largest

public int getSmallestBox(int boxsize,ArrayList<BoxItems> items)
{
    if(productsFit(boxsize -1)!= null)
    {
        return getSmallestBox(boxsize -1, items)
    }
    else
        return boxsize;
}

这将得到我们可以放入物品的最小盒子。您需要检查的最后一件事是组合框。你可能会发现你有 4 个小盒子，你可以将它们组合成 2 个中号盒子。在您可以组合和收缩框之后，您就可以在每个运行之后监控结果。所以整个程序流程在粗略的伪代码中看起来像这样。

Container[getInitBoxCount()] shipments //create an array of containers with the size of the inital box count 

for(Container c : shipments)
{
    c = new LargeContainer();
}


Container[] check; //create new objects into the check array. dont set one array = to anoter

do
{
    check = shipments //create new objects into the check array. dont set one array = to anoter
    for(Container c: shipments)
        getSmallestBox(5, c);
    combineBoxes(shipments);
}
while(check == shipments)

Answer 4

对于当前版本，这有效：

@Test
void testIssue158() {
    List<Container> containers = new ArrayList<>();
    containers.add(new Container("X",10, 10, 5, 1000));

    List<BoxItem> products = new ArrayList<>();
    for(int i = 0; i < 1000; i++) {
        products.add(new BoxItem(new Box(Integer.toString(i), 1, 1, 1, 1)));
    }

    LargestAreaFitFirstPackager packager = new LargestAreaFitFirstPackager(containers, false, true, true);
    List<Container> fits = packager.packList(products, 50, Long.MAX_VALUE);
    assertNotNull(fits);
    assertEquals(fits.size(), 2);
}

希望这意味着没有适合多容器的自定义解决方法！

如何创建将继续运行算法直到在 Java 中成功的算法

How to create an algorithm that will continue running an algorithm until success in Java

java

algorithm

bin-packing

如何创建将继续 运行 算法直到在 Java 中成功的算法

How to create an algorithm that will continue running an algorithm until success in Java

java

algorithm

bin-packing

如何创建将继续运行算法直到在 Java 中成功的算法