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

Recursive Backtracking HELP!

post #1 of 3
Thread Starter 
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 \
");
solution.add(possibleOrders.min());
lengthLeft -= possibleOrders.min();
possibleOrders.remove(possibleOrders.min());
}
else
{
possibleOrders.remove(possibleOrders.min());
}
try{
  Thread.sleep(10); //sleep 1000 milliseconds
  }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 \
");
possibleOrders.add(solution.min());
solution.remove(solution.min());
}
solution.add(value);
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())
    {
    solution.add(value);
    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 
  hide details  
Reply
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 
  hide details  
Reply
post #2 of 3
Quote:
Originally Posted by gilljoy View Post
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 
  hide details  
Reply
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 
  hide details  
Reply
post #3 of 3
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 
  hide details  
Reply
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 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Recursive Backtracking HELP!