我想創建一個函式來確定父紙張尺寸上的最多紙張數
上面的公式仍然不是最優的。如果使用上述公式最多只能產生 32 個裁切/張。我想要像下面這樣。
uj5u.com熱心網友回復：
這似乎是一個很難以最佳方式解決的問題。請參閱http://lagrange.ime.usp.br/~lobato/packing/以討論 2008 年的一篇論文，該論文聲稱該問題被認為（但未證明）是 NP-hard。研究人員找到了一些近似演算法并在該網站上實作了它們。
uj5u.com熱心網友回復：
以下解決方案使用自上而下的動態規劃來找到此問題的最佳解決方案。我在 C# 中提供了這個解決方案，轉換成你選擇的語言（或你喜歡的任何風格的偽代碼）應該不會太難。我已經在您的具體示例中測驗了此解決方案，它在不到一秒鐘的時間內完成（我不確定比一秒鐘少多少）。
需要注意的是，該解決方案假設只允許使用斷頭臺切割。這是現實世界 2D Stock-Cutting 應用程式的常見限制，它極大地簡化了解決方案的復雜性。但是，CS、數學和其他編程問題通常允許所有型別的切割，因此在這種情況下，此解決方案不一定會找到最佳解決方案（但它仍然會提供比您當前的公式更好的啟發式答案）。
首先，我們需要一個值結構來表示起始庫存的大小、所需的矩形和從庫存中切割的部分（這需要是一個值型別，因為它將用作我們的關鍵memoization 快取和其他集合，我們需要比較實際值而不是物件參考地址）：
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)
main 方法為此類問題呼叫通用求解器方法（不僅限于一個大小的矩形及其旋轉）：
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;
}
}
正如我在評論中提到的，實際上很容易將這個類從代碼中分解出來，但它現在仍然存在。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395978.html
標籤：算法