Finding the numbers from a set which give the minimum amount of waste

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;

      }
  }
11
задан Bill the Lizard 16 September 2012 в 15:48
поделиться