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

Question

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;

      }
  }

Answer 1

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.