Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Recursive Backtracking HELP!
New Posts  All Forums:Forum Nav:

# Recursive Backtracking HELP!

Hey all,

I'm in abit of a pickle. I've got to implement a recursive backtracking algorithm that will work out how to cut a bar with the least ammount of wasteage.

this is from the specification for the coursework.

Quote:
Now, imagine the scenario in which a factory manufactures steel bars of length 150mm. Its cutting shop receives orders for cut lengths of bars, which must be met by cutting up the manufactured bars. With each order the factory wants to cut the bar is such a way that it produces the least amount of wastage.

Develop a java method which given manufactured bar of length 150mm, a set of all orders in the order list and an empty set produces the set of orders which can be met by cutting up the bar with minimum wastage.
currently I've sort of got it working non recursively but not 100% and when I try and get it working recurisvely it just crashed lol infinite loop / stack overflow I think.

Would anyone mind looking at my code and giving me a hand? its for uni coursework and its the first time i've really tryed recursive backtracking so any help would be brilliant.

Non recursive code that sort of works.

Code:
``````private SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthLeft)
{
//SetInt possibleOrders = solution.clone();

while(!possibleOrders.isEmpty())
{

if(possibleOrders.min()<= lengthLeft)
{
if(possibleOrders.min() > solution.min())
{
System.out.println(possibleOrders.min() + "added to solution \
");
lengthLeft -= possibleOrders.min();
possibleOrders.remove(possibleOrders.min());
}
else
{
possibleOrders.remove(possibleOrders.min());
}
try{
}catch(Exception e){}
}

else if(possibleOrders.min() > lengthLeft)
{
System.out.println("poss order min" + possibleOrders.min()+"\
");
System.out.println("solution min" + solution.min()+"\
");
if(possibleOrders.min() > solution.min())
{
int value = possibleOrders.min();
while(value > lengthLeft)
{
lengthLeft += solution.min();
System.out.println(solution.min() + "added to possible orders \
");
solution.remove(solution.min());
}
possibleOrders.remove(value);
lengthLeft -= value;
}
else
{
possibleOrders.remove(possibleOrders.min());
}
}

}
System.out.print("Solution :");
solution.printNumbers();
System.out.println("Wastage :" + lengthLeft);
return solution;
}``````

My attempt at recursive code

Code:
``````private SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthLeft)
{
while(!possibleOrders.isEmpty())
{
System.out.println("not empty");
int value = possibleOrders.min();
if(value < lengthLeft && value>solution.min())
{
possibleOrders.remove(value);
lengthLeft-=value;

if(!possibleOrders.isEmpty())
{
possibleOrders.tryCutting(possibleOrders,solution,lengthLeft);
}
else
break;
}
}
return solution;
}``````
 i7 930 and GTX570 (14 items)
CPUMotherboardGraphicsRAM
Intel core i7 930 Gigabyte GA-X58-USB3.0 Gigabyte 7970 Ghz Edition 6gb corsair
Hard DriveOptical DriveCoolingPower
1tb samsung LG Blu-ray Thermalright Ultra Extreme 120 XFX 850W Black Edition
Case
Xigmatek Midgard
 i7 930 and GTX570 (14 items)
CPUMotherboardGraphicsRAM
Intel core i7 930 Gigabyte GA-X58-USB3.0 Gigabyte 7970 Ghz Edition 6gb corsair
Hard DriveOptical DriveCoolingPower
1tb samsung LG Blu-ray Thermalright Ultra Extreme 120 XFX 850W Black Edition
Case
Xigmatek Midgard
Quote:
 Originally Posted by gilljoy My attempt at recursive code Code: ``````private SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthLeft) { while(!possibleOrders.isEmpty()) { System.out.println("not empty"); int value = possibleOrders.min(); if(value < lengthLeft && value>solution.min()) { solution.add(value); possibleOrders.remove(value); lengthLeft-=value; if(!possibleOrders.isEmpty()) { possibleOrders.tryCutting(possibleOrders,solution,lengthLeft); } else break; } } return solution; }``````
The first problem you have is you have a while loop with only an IF statement that removes possible orders. In the event you have more or an equal amount of length ordered compared to what you have left, your code stops removing orders and just loops forever. Also, you should change "value < lengthLeft" to "value <= lengthLeft", and then add an ELSE statement that handles if the length order is greater than what is available, it must do something else, like start with a new full 150mm bar. Also I am not completely sure why you are checking that value>solution.min(). It seems like you are only going to process an order if it is greater than the minimum solution length. I don't fully understand what you are trying to do there.
 i7 (13 items)
CPUMotherboardGraphicsRAM
Intel Core i7 920 D0 w/ HT On [4.01ghz @ 1.208v] Asus P6X58D Premium Asus HD5870 G.SKILL 6GB (3X2GB) DDR3 @ 1528MHz
Hard DriveOptical DriveOSMonitor
OCZ Vertex Turbo 60GB FW1.5 2xSamsung Spinpoint F3 LG 8x Blu-ray Combo Drive Windows 7 64-bit Dell U2410 Rev. A04
PowerCase
OCZ ModXStream Pro 700W V2.2 HAF 922
 i7 (13 items)
CPUMotherboardGraphicsRAM
Intel Core i7 920 D0 w/ HT On [4.01ghz @ 1.208v] Asus P6X58D Premium Asus HD5870 G.SKILL 6GB (3X2GB) DDR3 @ 1528MHz
Hard DriveOptical DriveOSMonitor
OCZ Vertex Turbo 60GB FW1.5 2xSamsung Spinpoint F3 LG 8x Blu-ray Combo Drive Windows 7 64-bit Dell U2410 Rev. A04
PowerCase
OCZ ModXStream Pro 700W V2.2 HAF 922
At glance (sorry didn't have much time to read through it). This line:

Code:
``possibleOrders.tryCutting(possibleOrders,solution,lengthLeft);``
Might need to have a return in front of it.

Code:
``return possibleOrders.tryCutting(possibleOrders,solution,lengthLeft);``
Because otherwise you're not returning the value out of tryCutting because to the last caller of it.
Edited by lordikon - 4/28/11 at 11:37am
 Foldatron (17 items) Mat (10 items) Work iMac (9 items)
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000
PowerCase
750W PC P&C Silencer CoolerMaster 690
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard
Mouse
Mac wireless mouse
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display
Monitor
27" Apple thunderbolt display
 Foldatron (17 items) Mat (10 items) Work iMac (9 items)
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000
PowerCase
750W PC P&C Silencer CoolerMaster 690
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard
Mouse
Mac wireless mouse
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display
Monitor
27" Apple thunderbolt display
New Posts  All Forums:Forum Nav:
Return Home
Back to Forum: Coding and Programming
• Recursive Backtracking HELP!
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Recursive Backtracking HELP!