Добрый день!
Дана задача: Существует N контейнеров, в каждый помещается ровно 1 кг какого-нибудь груза (объем груза значения не имеет). Есть M предметов, вес каждого предмета от 0 до 1 кг (объем не имеет значения).
Стоит задача о распределении этих предметов по контейнерам, чтобы количество используемых контейнеров было минимально возможным. Предполагается, что количество контейнеров и количество предметов может быть довольно большим (N <= 1000, M <=10000). Если предметы разложить не удается (например, суммарный вес предметов больше чем N кг), то выдать сообщение об этом.

Я её решила так: Вначале отсортировала массив предметов, которые надо положить в контейнеры; потом шла по отсортированному массиву с начала и конца, собирая большой предмет и сколько помещается к нему маленьких.

Получилась довольно большая сложность у алгоритма.

Как можно уменьшить сложность алгоритма? Какие ещё варианты решения существуют?





Приложение:
bool Distribution(int*thing, int container,int size)
{
int i = 0, j = size - 1;
while ( i != j && j > i)
{
if (container > 0)
{

int sum = thing[j] + thing[i];

if (thing[j] == 1000)
{

container--;
}
else
{
if (sum >= 1000)
{
container--;
i--;

}
else
{

bool flag = false;
while (sum < 1000)
{
i++;
sum += thing[i];
flag = true;

}
container--;
if (flag)i--;

}
}

i++;
j--;
}
else
{
return false;
break;
}

}

return true;
}