Блог

Я обнаружил эту проблему: предположим, что у меня есть поля с N яблонями, на каждом из которых есть _i яблок. У меня также есть M basket, каждая корзина обладает свойством C _i для емкости и F _i для гибкости. Когда я собираюсь выбирать яблони, я могу выбирать только из дерева в порядке от 1 до N. У каждого дерева у меня есть два варианта: выбрать все яблоки на дереве или расширить мою корзину, чтобы увеличить ее вместимость на F. Когда я разворачиваю корзину, я не могу выбрать фрукты в этом дереве. Найдите максимальное количество яблок, которые можно собрать в каждой корзине.

Пример:

N = 5; A = [3, 2, 4, 7, 5]

M = 2; (C, F) = [(5,3), (3,6)]

Ответ: Для первой корзины максимальное количество полученных яблок равно 12:

1. Расширьте пакет на 3 (максимальная вместимость = 5 3 = 8)
2. Увеличьте пакет на 3 (максимальная вместимость = 8 3 = 11)
3. Увеличьте пакет на 3 (максимальная вместимость = 11 3 = 14)
4. Выберите 4-е дерево (получите 7 яблок, текущее общее количество = 7)
5. Выберите 5-е дерево (получите 5 яблок, текущее общее количество = 12)

А для второго пакета максимум равен 15:

1. Выберите 1-е дерево (получите 3 яблока, текущее общее количество = 3)
2. Расширьте пакет на 6 (максимальная вместимость = 3 6 = 9)
3. Расширьте пакет на 6 (Максимальная вместимость = 9 6 = 15).
4. Выберите 4-е дерево (получите 7 яблок, текущее общее количество = 10)
5. Выберите 5-е дерево (получите 5 яблок, текущее общее количество = 15)

Как мне следует подойти к решению этой проблемы?

Это поможет представить эту проблему как рекуррентное отношение:

Допустим, есть функция MaxApples(treeNum, capacityLeft) , которая дает вам максимальное количество яблок, которое вы можете получить для данной корзины.

Начальные параметры для этой функции будут treeNum = 0 такими, потому что вы начинаете с первого дерева и capacityLeft = C for the given basket потому, что корзина пуста и еще не развернута.

Затем для каждого дерева у вас есть 2 варианта — либо развернуть корзину, либо выбрать дерево. Это может быть представлено 2 рекурсивными вызовами, в MaxApple которых при первом выборе вы увеличиваете номер дерева и увеличиваете емкость F (на сколько расширяется корзина). Другой вариант — добавить все яблоки из текущего дерева в вашу корзину, а затем при рекурсивном вызове увеличить treeNum и уменьшить емкость на то, сколько вы только что выбрали.

Примечание: на каждом этапе вам нужно будет проверять, есть ли у вас выбор выбора или нет. То есть проверьте, больше или равно ли значение capacityLeft для дерева, которое вы хотите выбрать.

Вы можете рассчитать общее количество, которое вы получите от обоих из них, и просто использовать его по максимуму.

Вот приведенный ниже код на Java (только для одной корзины):

 class Main {

  static int[] trees = new int[]{3, 2, 4, 7, 5};
  static int basketCapacity = 5;
  static int basketFlex = 3;

  public static void main(String[] args) {
    System.out.println(maxApples(0, basketCapacity));
  }

  public static int maxApples(int treeNum, int capacityLeft) {
    if (treeNum >= trees.length) {
      return 0;
    }

    int pick = 0;
    if (trees[treeNum] <= capacityLeft) {
      pick = trees[treeNum]   maxApples(treeNum 1, capacityLeft - trees[treeNum]);
    }
    int expand = maxApples(treeNum 1, capacityLeft   basketFlex);

    return Math.max(pick, expand);
  }
}
  

Я думаю, что это должно было стать проблемой возврата. Прежде всего, я рекомендую вам ознакомиться с общим описанием этого. https://en.wikipedia.org/wiki/Backtracking

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