Stacking и динамическое программирование

Question

В основном я пытаюсь решить эту проблему:

Дано N блок куба блоков, найти меньшее количество стопок, чтобы сделать для того, чтобы использовать все блоки. Куча - это куб или пирамида. Например, две действительные сваи - это куб 4 * 4 * 4 = 64 с использованием 64 блоков, а пирамида 1² + 2² + 3² + 4² = 30 с использованием 30 блоков.

Однако я не могу найти подходящий угол для его приближения. Я чувствую, что он похож на проблему с рюкзаком, но все же не смог найти реализацию.

Любая помощь была бы высоко оценена!

Answer 1

Сначала я дам рекуррентное отношение, которое позволит решить проблему рекурсивно. Учитывая N, пусть

SQUARE-NUMS 
TRIANGLE-NUMS 

подмножество квадратных чисел и треугольных чисел в {1,...,N} соответственно. Пусть PERMITTED_SIZES - объединение этих. Обратите внимание, что, поскольку 1 встречается в PERMITTED_SIZES, любой экземпляр возможен и дает неотрицательный оптимум.

Функция follwing в псевдокоде решает проблему в вопросе рекурсивно.

int MinimumNumberOfPiles(int N) 
{ 
    int Result = 1 + min { MinimumNumberOfPiles(N-i) } 
    where i in PERMITTED_SIZES and i smaller than N; 
    return Result; 
} 

Идея заключается в том, чтобы выбрать разрешенный размер бен для элементов, удалить эти элементы (что делает экземпляр проблемы меньше) и решить рекурсивно для небольших экземпляров. Чтобы использовать динамическое программирование, чтобы обойти множественную оценку одной и той же подзадачи, нужно было бы использовать одномерное пространство состояний, а именно массив A[N], где A[i] - минимальное количество свай, необходимых для блоков блоков i. Используя это пространство состояний, проблему можно решить итеративно следующим образом.

for (int i = 0; i < N; i++) 
{ 
    if i is 0 set A[i] to 0, 
    if i occurs in PERMITTED_SIZES, set A[i] to 1, 
    set A[i] to positive infinity otherwise; 
} 

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

for (int i = 0; i <= N; i++) 
{ 
    if (A[i] is positive infinity) 
    { 
     A[i] = 1 + min { A[i-j] : j is in PERMITTED_SIZES and j is smaller than i } 
    } 
} 

Требуемое оптимальное значение будет найдено в A[N]. Обратите внимание, что этот алгоритм вычисляет только минимальное количество свай, но не самих свай; если требуется подходящий раздел, он должен быть найден либо путем обратного отслеживания, либо путем поддержки дополнительных вспомогательных структур данных.

В общей сложности, при условии, что PERMITTED_SIZES известно, что проблема может быть решена в O(N^2) шагов, так как PERMITTED_SIZES содержит не более N значений.

Эту проблему можно рассматривать как адаптацию Rod Cutting Problem, где каждый квадрат или треугольник, размер имеет значение 0 и любой другой размер имеет значение 1, а цель состоит в том, чтобы свести к минимуму общую стоимость.

В общей сложности для генерации PERMITTED_SIZES требуется дополнительная стоимость расчета.

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

int i = N; // i is the total amount still to be distributed 
while (i > 0) 
{ 
    choose j such that 
    j is in PERMITTED_SIZES and j is smaller than i 
    and 
    A[i] = 1 + A[i-j] is minimized 
    Output "Take a set of size" + j; // or just output j, which is the set size 

    // the part above can be commented as "let's find out how 
    // the value in A[i] was generated" 

    set i = i-j; // decrease amount to distribute 
}