Шаг 1

Для начала создадим нашу таблицу, словно мы решаем задачу «руками» — проходимся по алгоритму и исполняем его «в голове». Будем выводить её результат в конце функции, чтобы убедиться, что мы получаем то же самое, что насчитали «руками».

import {logResult, logTable} from "./logger";

// Напишем нашу функцию для оптимизации, принимающую массив размеров частей и размер пачки
function prioritize(filePartSizes, chunkSize) {
  // создаем нашу табличку
  const table = Array(filePartSizes.length).fill( Array(chunkSize).fill(0) );


  logTable(table);

  // Результат — нижняя правая ячейка
  return table[filePartSizes.length - 1][chunkSize - 1];
}

logResult(prioritize([4, 5, 7], 10));

Шаг 2

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

import {logResult, logTable} from "./logger";

// Напишем нашу функцию для оптимизации, принимающую массив размеров частей и размер пачки
function prioritize(filePartSizes, chunkSize) {
  // создаем нашу табличку
  const table = Array(filePartSizes.length).fill().map(() => Array(chunkSize).fill(0));

  // Заполняем каждую строчку последовательно
  for (let rowIndex = 0; rowIndex < filePartSizes.length; rowIndex++) {
    for (let cellIndex = 0; cellIndex < chunkSize; cellIndex++) {
      const currentChunkSize = cellIndex + 1;
      const currentFilePartSize = filePartSizes[rowIndex];

      // считаем максимальное количество места, которое мы можем занять частями текущего размера
      const maximumCurrent = Math.floor(currentChunkSize / currentFilePartSize) * currentFilePartSize;

      // максимальное количество данных, которое мы можем положить в оставшееся количество места
      // берем максимум решения предыдущей подзадачи для оставшегося места если оно есть, либо 0
      const maximumRest = table[rowIndex - 1] && table[rowIndex - 1][cellIndex - maximumCurrent] || 0;

      // получаем общее решение для данной ячейки
      const solution = maximumCurrent + maximumRest;

      table[rowIndex][cellIndex] = solution;
    }
  }

  logTable(table);

  // Результат — нижняя правая ячейка
  return table[filePartSizes.length - 1][chunkSize - 1];
}

logResult(prioritize([4, 5, 7], 10));

Шаг 3

Добавим операцию максимума над текущим и предыдущим решением и получим таблицу, идентичную той, что мы заполняли «руками»!

import {logResult, logTable} from "./logger";

// Напишем нашу функцию для оптимизации, принимающую массив размеров частей и размер пачки
function prioritize(filePartSizes, chunkSize) {
  // создаем нашу табличку
  const table = Array(filePartSizes.length).fill().map(() => Array(chunkSize).fill(0));

  // Заполняем каждую строчку последовательно
  for (let rowIndex = 0; rowIndex < filePartSizes.length; rowIndex++) {
    for (let cellIndex = 0; cellIndex < chunkSize; cellIndex++) {
      const currentChunkSize = cellIndex + 1;
      const currentFilePartSize = filePartSizes[rowIndex];

      // считаем максимальное количество места, которое мы можем занять частями текущего размера
      const maximumCurrent = Math.floor(currentChunkSize / currentFilePartSize) * currentFilePartSize;

      // максимальное количество данных, которое мы можем положить в оставшееся количество места
      // берем максимум решения предыдущей подзадачи для оставшегося места если оно есть, либо 0
      const maximumRest = table[rowIndex - 1] && table[rowIndex - 1][cellIndex - maximumCurrent] || 0;

      // получаем общее решение для данной ячейки
      const solution = maximumCurrent + maximumRest;

      // Если есть, с чем сравнить текущее решение — сравниваем и берем максимум
      table[rowIndex][cellIndex] = rowIndex > 0
        ? Math.max(solution, table[rowIndex - 1][cellIndex])
        : solution;
    }
  }

  logTable(table);

  // Результат — нижняя правая ячейка
  return table[filePartSizes.length - 1][chunkSize - 1];
}

logResult(prioritize([4, 5, 7], 10));

Шаг 4

Итак, мы реализовали нашу функцию. В прошлой статье мы заверили вас, что ни от изменения частей местами, ни от добавления новых алгоритмов решение не сломается. Давайте посмотрим на решение этой задачи с другими аргументами. Всё ещё работает!

import {logResult, logTable} from "./logger";

// Напишем нашу функцию для оптимизации, принимающую массив размеров частей и размер пачки
function prioritize(filePartSizes, chunkSize) {
  // создаем нашу табличку
  const table = Array(filePartSizes.length).fill().map(() => Array(chunkSize).fill(0));

  // Заполняем каждую строчку последовательно
  for (let rowIndex = 0; rowIndex < filePartSizes.length; rowIndex++) {
    for (let cellIndex = 0; cellIndex < chunkSize; cellIndex++) {
      const currentChunkSize = cellIndex + 1;
      const currentFilePartSize = filePartSizes[rowIndex];

      // считаем максимальное количество места, которое мы можем занять частями текущего размера
      const maximumCurrent = Math.floor(currentChunkSize / currentFilePartSize) * currentFilePartSize;

      // максимальное количество данных, которое мы можем положить в оставшееся количество места
      // берем максимум решения предыдущей подзадачи для оставшегося места если оно есть, либо 0
      const maximumRest = table[rowIndex - 1] && table[rowIndex - 1][cellIndex - maximumCurrent] || 0;

      // получаем общее решение для данной ячейки
      const solution = maximumCurrent + maximumRest;

      // Если есть, с чем сравнить текущее решение — сравниваем и берем максимум
      table[rowIndex][cellIndex] = rowIndex > 0
        ? Math.max(solution, table[rowIndex - 1][cellIndex])
        : solution;
    }
  }

  logTable(table);

  // Результат — нижняя правая ячейка
  return table[filePartSizes.length - 1][chunkSize - 1];
}

logResult(prioritize([8, 5, 4, 7], 11));

File logger.js

const table = document.getElementById('table');
const result = document.getElementById('result');


export function logTable(data) {
  const body = document.createElement('tbody');

  for (const line of data) {
    const lineElement = document.createElement('tr');

    for (const cell of line) {
      const cellElement = document.createElement('td');

      cellElement.innerText = cell;

      lineElement.appendChild(cellElement);
    }

    body.appendChild(lineElement);
  }

  table.appendChild(body);
}

export function logResult(res) {
  result.innerText = `Максимальное количество занимаемого места — ${res} МБ`;
}