Нахождение чисел из набора, которые дают минимальное количество отходов

Question

Набор передается этому методу ниже, и длина стержня также передается. Решение должно выводить числа из набора, которые дают минимальное количество отходов, если определенные числа из набора были удалены из барадлина.Итак, длина бара 10, набор включает в себя 6,1,4, таким образом, решение - это 6 и 4, а потери - 0. У меня возникли некоторые проблемы с условиями возврата обратно через набор.Я также пытался использовать «глобальную» переменную потерь, чтобы помочь с аспектом обратного отслеживания, но безрезультатно.

SetInt - реализованная вручную реализация набора, которая может добавлять, удалять, проверять, пуст ли набор и возвращатьминимальное значение из набора.

/*
 * 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

У вас есть пара проблем.

Одна из этих строк: int a = clonedSet.min(); //select next candidate

Если вы пройдете по вашему примеру, он найдет значение 1 и сначала его использует, поэтому1 и 4 были бы использованы, но 6 не были бы.

Вы лучше ищете максимальное значение, которое будет <= оставшаяся длина. </p>

Эта строка также странная для меня:

WASTAGE +=a;

Я думаю, вы должны вычитать, и почему вы изменяете статическое целое число?

Если это что-то, что может быть изменяемым, то вам следуетпросто передайте его, а затем вернитесь, когда вы закончите, сколько было потрачено, поэтому верните новый класс, решение и потерянную сумму.

Для рекурсии вам понадобится вашНапример, затем пройдитесь по одному за раз и посмотрите, соответствует ли его поведение ожидаемому.

Возможно, вы захотите посмотреть на этот цикл:

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

Как, если вы делаете это рекурсивно, то, если у вас есть 3 возможных решения, выЯ полагаю, что в итоге я выполню 6 тестов, а не трижды, что вы ожидаете.

Если вы удалите цикл for, все равно все будет в порядке.Вставьте заявление для печати, чтобы вы могли наблюдать его каждый раз.

ОБНОВЛЕНИЕ:

Основываясь на дополнительной информации, вам нужно собрать всевозможные решения, то, что вы можете сделать, это пройти и сделать первый проход, получить решения, которые работают таким образом.Затем сдвиньте влево или вправо возможные решения, затем повторите попытку.

Когда вы полностью переместились, вы попробуете различные комбинации, но не все возможные комбинации, но затем вы сможете принять эти решения.и посмотрите, какой из них оптимален.

Если вы хотите протестировать больше комбинаций, то вам нужно будет циклически удалить элемент, и это может быть рекурсивным.

Итак, вы будетенужна одна рекурсивная функция внутри другой, поэтому вы рекурсивно просматриваете все возможные комбинации, а затем рекурсивно ищите решение проблемы.

Я думаю, что поиск max, вероятно, будет лучшим, но этотолько мое внутреннее чувство, и можно показать, что min лучше.

Answer 2

Я согласен с Джеймсом, тебе не нужна / не нужна петля.Насколько я понимаю, ваш алгоритм tryCutting берет список возможных заказов, текущее рассматриваемое решение и оставшуюся длину, если вы хотите сократить текущее решение.Затем вам необходимо:

• удалить кратчайший срез из ордеров.Если это больше, чем оставленная длина, не пытайтесь больше.В противном случае,
• первый случай: вы не выполняете этот разрез - попробуйте еще раз с новым списком заказов и той же текущей длиной
• второй случай: вы выполняетеэтот разрез.Добавьте его в текущее решение и попробуйте CutCutting с новым списком заказов и длиной, уменьшенной на этот отрезок.Наконец, снова снимите его с текущего решения (для возврата)
• поместите кратчайшее сокращение заказов (для возврата)

Теперь, для каждого попытки, проверьте длинупока против вашего лучшего мирового дела.Если короче, то обновите глобальное (клон) текущего решения.

Это даст вам одно лучшее решение или одно из них, если есть несколько одинаково хороших.Чтобы получить все решения, вам нужен глобальный список SetInts.Если вы найдете решение лучше текущего, очистите список и добавьте новое решение.Если он равен текущему лучшему, просто добавьте его.

Вот он в коде:

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
    }
}