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 nu开发者_开发问答mbers 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;

      }
  }

You have a couple of problems.

One is this line: int a = clonedSet.min(); //select next candidate

If you walk through your example, it would have found the value 1 and used that first, so 1 and 4 would have been used, but 6 wouldn't.

You are better looking for the max value that will be <= the remaining length.

This line also is odd to me:

WASTAGE +=a;

You should be subtracting I think, and why are you modifying a static integer?

If this is something that can be mutable, then you should just pass it in, then pass back when you are done what was the amount wasted, so have a new class that you return, the solution and the amount that was wasted.

For recursion you will want to have your example, then walk through one at a time and see if the behavior it does is what you expect.

You may want to look at this loop:

for (int i = 0; i < possibleOrders.numberInSet(); i++) // the repeat

As, if you are doing this recursively, then if you have 3 possible solutions, you will end up doing 6 tests, I believe, rather than going through three times, which is what you expect.

If you remove the for loop you should still be fine. Put in a print statement so you can watch it go through each time.

UPDATE:

Based on more information, what you will want to do is to collect all the possible solutions, then what you can do is to go through and do the first pass, get the solutions that work that way. Then, shift left or right the possible solutions, then try again.

When you have shifted all the way through, you will have tried various combinations, but not every possible combination, but, you can then take those solutions, and see which is optimal.

If you want to test more of the combinations, then you will need to loop through removing an item, and this could be recursive.

So, you will need one recursive function inside another one, so you recursively go through all possible combinations, then recursively look to find a solution to the problem.

I think looking for the max would probably be best, but that is just my gut feeling, and it could be shown that min is best.

I agree with James, you don't need/want the loop. As I understand it, your 'tryCutting' algorithm takes a list of possible orders, a current solution under consideration and the the length left if you were to cut the current solution. Then you need to:

• remove the shortest cut from the orders. If it's longer than the length left, don't try any more. Otherwise,
• first case: you don't fulfil that cut - tryCutting again with the new list of orders and the same current length
• second case: you do fulfil that cut. Add it to the current solution and tryCutting with the new list of orders and the length reduced by that cut. Finally take it off the current solution again (for backtracking)
• put the shortest cut back on the orders (for backtracking)

Now, for each case you try, check the length left against your global best case so far. It it's shorter then update a global with (a clone of) the current solution.

This will give you the single best solution or one of them if there are several equally good. To get all solutions you need a global list of SetInts. If you find a solution better than the current, clear the list and add the new solution. If it's equal to the current best, just add it.

Here it is in code:

public static void main(String[] args) {
    int[] nums = {6,1,4};          //Order Numbers
    int barLength = 10;         //Bar length
    bestSolution = new HashSet<SetInt>();
    bestWastage = barLength;
    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
    }
    tryCutting(possibleOrders, solution, barLength);
    for (SetInt result : bestSolution) {
        result.printNumbers();
    }

}

private static int bestWastage;
private static Set<SetInt> bestSolution;

private static void tryCutting(SetInt possibleOrders, SetInt solution, int lengthleft) {
    if (lengthleft < bestWastage) {
        // Better than the best solution
        bestWastage = lengthleft;
        bestSolution.clear();
        bestSolution.add(solution.cloneSet());
    } else if (lengthleft == bestWastage) {
        // Just as good as the best solution
        bestSolution.add(solution.cloneSet());
    }
    int a = possibleOrders.min(); //select next candidate
    if (a <= lengthleft) { // If acceptable
        possibleOrders.remove(a); // Remove it
        tryCutting(possibleOrders, solution, lengthleft); // Try without that cut
        solution.add(a); // add to the solution
        tryCutting(possibleOrders, solution, lengthleft - a); // Try with that cut
        solution.remove(a); // remove again
        possibleOrders.add(a); // add the candidate back on again
    }
}