A set is passed to this method below, and a length of a bar is also passed in. The solution should output the numbers from the set which give the minimum amount of waste if certain numbers from the set were removed from the bar length. So, bar length 10, set includes 6,1,4, so the solution is 6 and 4, and the wastage is 0. Im having some trouble with the conditions to backtrack though the set. Ive also tried to use a wastage "global" variable to help with the backtracking aspect but to no avail.
SetInt is a manually made set implementation, which can add, remove, check if the set is empty and return the minimum value from the set.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package recback;
public class RecBack {
public static int WASTAGE = 10;
public static void main(String[] args) {
int[] nums = {6,1,4};
//Order Numbers
int barLength = 10;
//Bar length
SetInt possibleOrders = new SetInt(nums.length);
SetInt solution = new SetInt(nums.length);
//Set Declarration
for (int i = 0; i < nums.length; i++)possibleOrders.add(nums[i]);
//Populate Set
SetInt result = tryCutting(possibleOrders, solution, barLength);
result.printNumbers();
}
private static SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft)
{
SetInt clonedSet = possibleOrders.cloneSet(); //initialise selection of candidates
for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat
{
int a = clonedSet.min(); //select next candidate
if (a <= lengthleft) //if accecptable
{
solution.add(a); //record candidate
lengthleft -= a;
clonedSet.remove(a); //remove from original set
if (!clonedSet.isEmpty()) //solution not complete
{
WASTAGE +=a;
tryCutting(clonedSet, solution, lengthleft);//try recursive call
if (lengthleft > WASTAGE)//if not successfull
{
WASTAGE += a;
solution.remove(a);
}
} //solution not complete
}
} //for loop
return solution;
}
}