2022 [8-10] Blockchain
Существует система хранения документов, построенная на основе связного списка блоков (блокчейн). Блоки состоят из набора транзакций и информации о предыдущем блоке цепочки. Каждая транзакция описывает добавляемый в систему один или несколько документов и содержит следующую информацию в формате JSON:
– номер транзакции (_id),
– автор документа (from),
– адресаты документов (to),
– объемы документов (value).
Размер транзакции определяется суммарным количеством авторов и адресатов документов, входящих в её состав.
Например, транзакция 11, описывающая документ автора ‘user01’ для ‘user02’ объемом 15 страниц
{
_id: 11,
from: "user01",
to: [ "user02" ],
value: [ 15 ]
}
имеет размер, равный двум.
Транзакция 12, описывающая два документа автора ‘user01’: один для ‘user02’ объемом 15 страниц, второй – для ‘user03’ объемом 10 страниц
{
_id: 12,
from: "user01",
to: [ "user02", "user03" ],
value: [ 15, 10 ]
}
имеет размер, равный трем.
Блок, сформированный на основе транзакций 11 и 12 будет иметь размер, равный 2 + 3 = 5, и суммарный объем документов, равный 15 + 15 +10 = 40.
Все незафиксированные транзакции хранятся в специальном хранилище, откуда их можно взять и добавить в новый блок. В один блок нельзя добавить транзакции с одинаковыми идентификаторами (_id). Также у блока есть ограничение на максимальный суммарный размер всех входящих в него транзакций – S = 15.
Сформируйте новый блок для добавления в блокчейн из числа незафиксированных транзакций так, чтобы общий объем документов, входящих в его транзакции, был максимальным. В ответе укажите перечень транзакций, входящих в блок, а также общий объем документов из выбранных транзакций.
К задаче прилагается:
storage_v1.json – содержимое хранилища незафиксированных транзакций в формате JSON.
Показать подсказку
А какие транзакции самые ценные с точки зрения объема на единицу размера?
Показать решение
Для решения задачи необходимо найти такой набор транзакций, сумма размеров которых равна 15, а объем которых максимальный. Для этого можно заранее посчитать размер и объем каждой транзакции, отсортируем по размеру транзакции по убыванию.
Способ 1.
Найдем относительную ценность каждой транзакции, полученную путем разделения объема транзакции на ей размер, и отсортируем в порядке убывания ценности.
Дальше набираем наиболее ценные транзакции так, чтобы суммарный размер был равен 15: ID 29 и 4 дают объем 87+98 = 185 и размер 4+5 = 9.
ID 29 может быть заменена комбинацией транзакций с размерами 2 + 2: ID 3 и ID 9. Тогда суммарный объем будет 21 + 17 = 38, что меньше объема транзакции с ID 29 (87).
ID 4 может быть заменена комбинацией транзакций с размерами 3 + 2: ID 6 и ID 3. Тогда суммарный объем будет 33 + 21 = 54, что меньше объема транзакции с ID 4 (98).
Остается 6 единиц, которые представляют собой комбинации 4+2 и 3+3. Найдем транзакции с таким размером и с максимальной ценностью:
4 + 2: ID 18 и 16 – 71 + 26 = 97.
3 + 3: ID 5 и 6 – 42 + 33 = 75.
В итоге получаем следующий набор:
(29,4,18,16) – суммарный объем равен
282.
Способ 2
Для поиска максимального объема выбранных транзакций можно написать программу, которая работает по следующему алгоритму.
1. Формируем массив значений объема заполненного блока размерами 1,2,…,15: V={V1, V2, … , VN}. Заполняем его нулями.
2. Берем очередную k-ю транзакцию с размером sk и объемом vk, и на её основе формируем новый массив значений объемов блока. Каждый i-й элемент массива равен максимум из следующих значений:
- предыдущего значения i-й ячейки массива (Vi);
- объема k-й транзакции vk, если она помещается в блок размером i (sk <= i) (то есть вместо того, что было берем текущую k-ю транзакцию, если её размер позволяет её добавить в блок размером i);
- суммы предыдущего (i-k)-го элемента массива, если k
3. Новый массив значений теперь рассматриваем как текущий массив V.
4. Выполняем пп.2-3, перебирая все имеющиеся транзакции k=1..30.
5. Максимальный объем блока будет содержаться в ячейке V15 массива значений объема блока.
В итоге получаем следующий набор: (29,4,18,16) – суммарный объем равен 282.
Показать ответ
Набор транзакций (29,4,18,16) – суммарный объем равен 282
<< Назад в раздел (Все задания)
