Recursive Backtracking / Knapsack Problem

[SCass2010]

Hi everyone,

As part of an assignment we have to develop a recursive backtracking solution in java to a sort of knapsack problem - you have a 150mm bar, a set of orders you have to cut and you need to come up with the best solution that gets the most orders done with the least amount of waste.

So far I have this as my recursive method

//	Returns the best possible solution where the most orders can be processed with
//	the least amount of wastage
    private SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthLeft)
 	{
 		int i = 7;
		//	while possibleOrders Set is not empty
		while (!possibleOrders.isEmpty())
		{	int order	= possibleOrders.min();
			System.out.println("Order Selected : " + order);
			System.out.println("Length Left    : " + lengthLeft);

			if (order <= lengthLeft)
			{
				solution.add(order);
				System.out.println(order + " Added To Solution");
				System.out.println(solution.numberInSet() + " Orders In Solution");
				possibleOrders.remove(order);
				lengthLeft -= order;
				System.out.println("New Length Left : " + lengthLeft);

				if(solution.numberInSet() != 7)
                {
                    tryCutting(possibleOrders,solution,lengthLeft);
                }
                else
                    break;
			}
			else
				break;
		}

 		return solution;
    }

But so far all it's good for is crashing your computer everytime you run it thanks to an infinite loop - it seems to take the first order from the set (3, 29, 25, 35, 20, 60, 40), then get stuck looping around and around trying to add 0 to the solution (we have to use a class SetInt where the value 0 is an illegal value)

Any help would be much appreciated, even just a hint in the right direction :)!

[SCass2010]

Just to explain a bit better - the possibleOrders.min() calls the first number in the set (we HAVE to use the SetInt class as it is, and theres no way of going through each value sadly :()

The way the SetInt class is, when you remove a value, it isn't really removed, it's just replaced with 0, so it was getting stuck as well looping forever trying to add 0, an illegal value that is not accepted when adding to the set

[bibiki]

I don't really have a solution, but I am writing because I want to subscribe to the thread and see the solution if someone finds it. however, I do have an idea.

If the length of all orders combined is less than the length of the bar, then the waste is always the same, regardless of the chronological order of responding to the orders.

For waste to vary, we'd have to have the combined length of all orders be longer than the bar. This is when the chronological order in which we respond to orders impacts the waste. So I guess you'd need an algorithm for ordering orders in different ways, and seeing which yields less waste. but in this case, I can't see how recursions helps... just ideas.