剪纸算法

Question

我想要创建一个函数来确定父纸大小上最多的纸片数。

​

​

上述公式仍然不是最优的。如果使用上述配方，最多只会产生32张剪纸。我想要像下面这样。

​

​

Answer 1

这似乎是一个很难最好地解决的问题。有关2008年一篇论文的讨论，请参见http://lagrange.ime.usp.br/~lobato/packing/，该论文声称这个问题被认为(但没有被证明)是NP难解决的。研究人员发现了一些近似算法，并在该网站上实现了这些算法。

Answer 2

下面的解决方案使用自顶向下动态规划来找到这个问题的最佳解决方案。我在C#中提供了这个解决方案，它应该不难转换成您所选择的语言(或者您喜欢的任何伪代码风格)。我已经在您的具体示例中测试了这个解决方案，它在不到一秒钟的时间内就完成了(我不确定有多少小于一秒钟)。

应该指出，此解决方案假定只允许使用断头台切割。这是一个常见的限制现实世界的二维股票切割应用，它大大简化了解决方案的复杂性。然而，CS、数学和其他编程问题通常允许所有类型的裁剪，因此在这种情况下，这个解决方案不一定能找到最优解(但它仍然会提供比当前公式更好的启发式答案)。

首先，我们需要一个值结构来表示起始库存的大小、所需的矩形和从股票中切割出来的部分(这需要值类型，因为它将用作回忆录缓存和其他集合的关键，我们需要比较实际值，而不是对象引用地址)：

public struct Vector2D
{
    public int X;
    public int Y;

    public Vector2D(int x, int y)
    {
        X = x;
        Y = y;
    }
}

下面是要调用的主要方法。请注意，所有的值都必须是整数，对于上面的具体情况，这只是意味着将所有的值乘以100。这里的这些方法需要整数，但在其他情况下是不变量的，因此乘以100或1000或任何不会影响性能的方法(只需确保这些值不会溢出int)。

    public int SolveMaxCount1R(Vector2D Parent, Vector2D Item)
    {
        // make a list to hold both the item size and its rotation
        List<Vector2D> itemSizes = new List<Vector2D>();
        itemSizes.Add(Item);
        if (Item.X != Item.Y)
        {
            itemSizes.Add(new Vector2D(Item.Y, Item.X));
        }

        int solution = SolveGeneralMaxCount(Parent, itemSizes.ToArray());
        return solution;
    }

下面是一个使用参数值调用此方法的示例。在这种情况下，我假设所有的解决方案方法都是一个名为SolverClass的类的一部分。

        SolverClass solver = new SolverClass();
        int count = solver.SolveMaxCount1R(new Vector2D(2500, 3800), new Vector2D(425, 550));
        //(all units are in tenths of a millimeter to make everything integers)

主方法调用这类问题的通用求解器方法(不限于一个大小的矩形及其旋转)：

    public int SolveGeneralMaxCount(Vector2D Parent, Vector2D[] ItemSizes)
    {
        // determine the maximum x and y scaling factors using GCDs (Greastest
        //  Common Divisor)
        List<int> xValues = new List<int>();
        List<int> yValues = new List<int>();
        foreach (Vector2D size in ItemSizes)
        {
            xValues.Add(size.X);
            yValues.Add(size.Y);
        }
        xValues.Add(Parent.X);
        yValues.Add(Parent.Y);

        int xScale = NaturalNumbers.GCD(xValues);
        int yScale = NaturalNumbers.GCD(yValues);

        // rescale our parameters
        Vector2D parent = new Vector2D(Parent.X / xScale, Parent.Y / yScale);
        var baseShapes = new Dictionary<Vector2D, Vector2D>();
        foreach (var size in ItemSizes)
        {
            var reducedSize = new Vector2D(size.X / xScale, size.Y / yScale);
            baseShapes.Add(reducedSize, reducedSize);
        }

        //determine the minimum values that an allowed item shape can fit into
        _xMin = int.MaxValue;
        _yMin = int.MaxValue;
        foreach (var size in baseShapes.Keys)
        {
            if (size.X < _xMin) _xMin = size.X;
            if (size.Y < _yMin) _yMin = size.Y;
        }

        // create the memoization cache for shapes
        Dictionary<Vector2D, SizeCount> shapesCache = new Dictionary<Vector2D, SizeCount>();

        // find the solution pattern with the most finished items
        int best = solveGMC(shapesCache, baseShapes, parent);

        return best;
    }

    private int _xMin;
    private int _yMin;

通用解决方案方法调用执行大部分实际工作的递归工作人员方法。

    private int solveGMC(
        Dictionary<Vector2D, SizeCount> shapeCache,
        Dictionary<Vector2D, Vector2D> baseShapes,
        Vector2D sheet )
    {
        // have we already solved this size?
        if (shapeCache.ContainsKey(sheet)) return shapeCache[sheet].ItemCount;

        SizeCount item = new SizeCount(sheet, 0);

        if ((sheet.X < _xMin) || (sheet.Y < _yMin))
        {
            // if it's too small in either dimension then this is a scrap piece
            item.ItemCount = 0;
        }

        else  // try every way of cutting this sheet (guillotine cuts only)
        {
            int child0;
            int child1;

            // try every size of horizontal guillotine cut
            for (int c = sheet.X / 2; c > 0; c--)
            {
                child0 = solveGMC(shapeCache, baseShapes, new Vector2D(c, sheet.Y));
                child1 = solveGMC(shapeCache, baseShapes, new Vector2D(sheet.X - c, sheet.Y));

                if (child0 + child1 > item.ItemCount)
                {
                    item.ItemCount = child0 + child1;
                }
            }

            // try every size of vertical guillotine cut
            for (int c = sheet.Y / 2; c > 0; c--)
            {
                child0 = solveGMC(shapeCache, baseShapes, new Vector2D(sheet.X, c));
                child1 = solveGMC(shapeCache, baseShapes, new Vector2D(sheet.X, sheet.Y - c));

                if (child0 + child1 > item.ItemCount)
                {
                    item.ItemCount = child0 + child1;
                }
            }

            // if no children returned finished items, then the sheet is
            //  either scrap or a finished item itself
            if (item.ItemCount == 0)
            {
                if (baseShapes.ContainsKey(item.Size))
                {
                    item.ItemCount = 1;
                }
                else
                {
                    item.ItemCount = 0;
                }
            }
        }

        // add the item to the cache before we return it
        shapeCache.Add(item.Size, item);

        return item.ItemCount;
    }

最后，采用GCD函数求解维数，以达到尺度不变性.这是在名为NaturalNumbers的静态类中实现的。我已经把这门课的主要部分包括在下面：

static class NaturalNumbers
{
    /// <summary>
    /// Returns the Greatest Common Divisor of two natural numbers.
    ///   Returns Zero if either number is Zero,
    ///   Returns One if either number is One and both numbers are >Zero
    /// </summary>
    public static int GCD(int a, int b)
    {
        if ((a == 0) || (b == 0)) return 0;
        if (a >= b)
            return gcd_(a, b);
        else
            return gcd_(b, a);
    }

    /// <summary>
    /// Returns the Greatest Common Divisor of a list of natural numbers.
    ///  (Note: will run fastest if the list is in ascending order)
    /// </summary>
    public static int GCD(IEnumerable<int> numbers)
    {
        // parameter checks
        if (numbers == null || numbers.Count() == 0) return 0;

        int first = numbers.First();
        if (first <= 1) return 0;

        int g = (int)first;
        if (g <= 1) return g;

        int i = 0;

        foreach (int n in numbers)
        {
            if (i == 0)
                g = n;
            else
                g = GCD(n, g);

            if (g <= 1) return g;
            i++;
        }
        return g;
    }

    // Euclidian method with Euclidian Division,
    //  From: https://en.wikipedia.org/wiki/Euclidean_algorithm
    private static int gcd_(int a, int b)
    {
        while (b != 0)
        {
            int t = b;
            b = (a % b);
            a = t;
        }
        return a;
    }

}

请让我知道任何问题或问题，您可能对此解决方案。

噢，忘了我也在用这门课：

public class SizeCount
{
    public Vector2D Size;
    public int ItemCount;

    public SizeCount(Vector2D itemSize, int itemCount)
    {
        Size = itemSize;
        ItemCount = itemCount;
    }
}

正如我在注释中提到的，将这个类从代码中剔除是非常容易的，但它现在仍然存在。