2509. Почтовое отправление
Для подготовки заключительного этапа Russian Code Cup
организаторам потребовалось отправить на место проведения n предметов. Для каждого предмета известна его масса в граммах mi.
Для отправки решено было воспользоваться почтовой службой
"Суперэкспресс". Служба принимает к пересылке бандероли, в каждой из
которых может пересылаться один или несколько предметов. При этом масса
бандероли равна сумме масс пересылаемых в ней предметов.
Пересылка бандероли стоит 1 рубль за грамм, за исключением
бандеролей, которые попадают под действие специального предложения. А именно,
если бандероль весит ровно один килограмм, то стоимость ее пересылки составляет
p рублей.
Организаторы Russian Code Cup хотят переслать все предметы,
затратив минимальную возможную сумму денег. Помогите им распределить предметы
по бандеролям, чтобы добиться этого.
Вход. Первая строка содержит два целых числа: n и p
(1 ≤ n ≤ 14; 1 ≤ p ≤ 1000) – количество предметов и
стоимость пересылки бандероли в рамках специального предложения. Вторая строка
содержит n целых чисел: m1, m2, ..., mn
(1 ≤ mi ≤ 1000
для всех i от 1 до n).
Выход. Выведите одно число – минимальную суммарную
стоимость пересылки всех предметов в рублях.
|
Пример
входа |
Пример
выхода |
5 800
100 200 300
400 500 |
1300 |
РЕШЕНИЕ
динамическое
программирование - маски подмножеств
Анализ алгоритма
Введем понятие маски, описывающую подмножество пересылаемых
предметов. Например, mask = 5 = 1012
соответствует подмножеству, которое включает в себя нулевой и второй предметы
(предметы будем нумеровать с нуля).
Для каждого
подмножества предметов вычислим их суммарный вес, равный стоимости пересылки.
Если он в точности равен 1000, то из того что p ≤ 1000, всегда следует воспользоваться специальным
предложением.
Пусть MinCost[mask] содержит
минимальную стоимость в рублях пересылки подмножества предметов, описываемых
маской mask. Тогда для
любого подмножества x, являющегося
подмножеством mask, имеет место соотношение
MinCost[mask] = 
Поскольку маска 2n
– 1 соответствует всему множеству из n
элементов, то ответом задачи будет значение MinCost[2n – 1].
Теорема. Перебор всех масок, а для них
подмасок выполняется за O(3n).
Доказательство 1. Рассмотрим i-ый бит. Для него имеется три варианта:
·
он входит в маску mask и подмаску sub;
·
он входит в маску mask но не входит в подмаску sub;
·
он не входит ни в маску mask, ни в подмаску sub;
Всего битов n, поэтому различных комбинаций 3n.
Доказательство 2. Пусть маска mask имеет k включенных битов. Тогда она будет иметь 2k подмасок. Количество масок длины n с k включенными битами
равно 
. Следовательно число комбинаций равно
= (1 + 2)n = 3n
Реализация алгоритма
Массы предметов
будем хранить в массиве m. В ячейке MinCost[mask] будем хранить минимальную стоимость в
рублях пересылки подмножества предметов, описываемых маской mask.
int m[15], MinCost[1 << 14];
Читаем входные
данные.
scanf("%d %d",&n,&p);
for(i = 0; i < n; i++) scanf("%d",&m[i]);
В переменной mask перебираем все возможные маски от 0 до 2n – 1.
for(mask = 0; mask < (1 << n);
mask++)
{
В переменную Cost занесем вес подмножества предметов, соответствующих маске mask. Просматриваем двоичный код числа mask. Если на его i-ой позиции находится 1, то включаем в Cost вес i-го предмета.
for(Cost
= i = 0; i < n; i++)
if (mask
& (1 << i)) Cost += m[i];
Если значение Cost строго равно 1000, то из того что p ≤ 1000
(дано по условию), следует присвоить переменной Cost значение p.
if (Cost
== 1000) Cost = p;
Занесем найденную стоимость пересылки
в соответствующую ячейку массива MinCost.
MinCost[mask] = Cost;
}
Для каждой маски mask перебираем все подмножества x Ì mask (x будет подмножеством mask
тогда и только тогда, когда mask AND x равно x). Если из множества, которому соответствует маска mask, вычесть множество соответствующее x, то получится множество с маской mask XOR x. Например, если mask =
11012, x = 10012
, то mask XOR x = 1002. Что соответствует теоретико - множественной
операции {1, 3, 4} \ {1, 4} = {3}.
for(mask = 0; mask < (1 << n);
mask++)
for(x = 0; x
< mask; x++)
Пересчитываем значение MinCost[mask] согласно приведенному в анализе
задачи рекуррентному соотношению.
if ((mask & x) == x)
MinCost[mask] = min(MinCost[mask],MinCost[mask^x] + MinCost[x]);
Выводим ответ, который находится в ячейке MinCost[2n – 1].
printf("%d\n",MinCost[(1
<< n) - 1]);
Реализация с оценкой O(3n)
#include <stdio.h>
#include <string.h>
#define MAX 0xFFFFFFFF
int n, p, Cost, i, mask, x;
unsigned int
m[15], MinCost[1 << 14];
unsigned int
min(unsigned int
i, unsigned int
j)
{
return (i
< j) ? i : j;
}
Для маски mask следует перебрать все подмаски sub, вычислим минимум среди всех возможных сумм FindCost(sub) + FindCost(mask ^ sub). Ввиду
симметрии суммы достаточно перебирать только те подмаски sub, для которых sub
≥ mask ^ sub.
unsigned int
FindCost(int mask)
{
if
(MinCost[mask] != MAX) return MinCost[mask];
// sub перебирает
все подмаски маски mask
for (int sub = (mask - 1) & mask;
sub >= mask ^ sub; sub = (sub -
1) & mask)
MinCost[mask] =
min(MinCost[mask], FindCost(sub) + FindCost(mask ^ sub));
return
MinCost[mask];
}
int main(void)
{
Установим MinCost[mask] = -1, если стоимость отправки набора предметов, которые задаются
подмножеством mask, еще не вычислена.
memset(MinCost,0xFF,sizeof(MinCost));
Читаем входные данные.
scanf("%d
%d",&n,&p);
for(i = 0; i
< n; i++) scanf("%d",&m[i]);
Если стоимость некоторого
подмножества предметов не больше 1000 (именно не больше, а не меньше так как
возможен случай p = 1000), то специальное
предложение для их отправки не может быть использовано. Для таких подмножеств
сразу можно вычислить MinCost[mask] как сумму стоимостей всех предметов. Если сумма стоимостей
предметов равна в точности 1000, то положим MinCost[mask] = p.
for(mask = 0;
mask < (1 << n); mask++)
{
for(Cost =
i = 0; i < n; i++)
if (mask
& (1 << i)) Cost += m[i];
if (Cost ==
1000) Cost = p;
if (Cost
<= 1000) MinCost[mask] = Cost;
}
Выводим ответ. Все множество
предметов задается маской 2n
– 1, двоичное представление которой состоит из n единиц.
printf("%u\n",FindCost((1
<< n) - 1));
return 0;
}