Сумма чисел в массиве, наиболее приближающаяся к необходимой , Заполнение интервала времени кусочками заданной длины

По идее должно быть просто, быстрый поиск в инете не дал результатов (не могу сформулировать точно).

Необходим алгоритм для наиболее полного заполнения времени кусочками заданной длины.

Скажем, дано 90 сек. Даны кусочки: 35, 30, 17, 13, 11. Если заполнять от больших к малым, получится 35 + 30 + 17 = 82. Эффективнее же было бы: 35 + 30 + 13 + 11 = 89.

Думаю, задача классическая, если что, скажите название (по-русски/английски), дальше сам разберусь, просто нет времени изобретать велосипед.

Спасибо.

Задача о рюкзаке

дальше разберусь, спасибо большое!

задача класса нп или п-спейс, не помню точно, можно решать перебором

Это не задача о рюкзаке. Рюкзак двупараметрический - вес, стоимость. В задаче о рюкзаке есть ограничение на размер суммарного веса и требуется найти выборку максимальной стоимости.

Это NP-полная задача "Сумма размеров".
1. Если размерность "средняя", то в Кормене описан приближённый алгоритм, на основе динамического программирования, по-моему.
2. Если размерность большая и сверхбольшая, могу дать свой собственный алгоритм, опубликованный в журнале "Мехатроника, автоматизация, управление". Я им отгружала готовую листопрокатную продукцию, набирала заданный вес пачками известного веса при заданной погрешности.

так и есть, у меня только "вес" есть (время). Если размерностью вы имеете в виду размер массива, то там порядка 10-20 штук. Пишется на яваскрипте, должно уложиться в 0,40 с (а желательно меньше). В инете по "сумме размеров" практического алгоритма особо не нашёл. Не махнёте рукой, где смотреть?

Ищите рюкзак и считайте вес=стоимость.

1. 10 штук можно сделать перебором, например, алгоритмом с возвратом (бэктрэкинг).

2. 20 штук тоже перебором можно сделать, но не уложитесь в указанное время.
Нужно делать динамическим программированием. Вычислительная сложность алгоритма O(nB), где n - количество слагаемых, B - набираемая сумма.

3. Если B - слишком большое, то вначале масштабируют, затем применяют динамическое программирование(Кормен). Метод заключается в уменьшении всех заданных величин s(a) и B в scale раз, где scale – коэффициент масштабирования, и последующим округлением до целого путем отбрасывания дробной части. Величина погрешности полученного таким образом решения не превосходит n*scale.

Куда махнуть рукой... Только в сторону Кормена.
В Кормене она называется Задача о сумме подмножеств Может, гуглить не Сумма размеров, а Сумма подмножеств?
Я для такой размерности особо ничего не искала, т.к. у меня размерность была сверхбольшая. Но знаю, что все методы для такой размерности основаны на динамическом программировании, в Кормене этот подход описан.

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

Добавлено 10.08.10, 21:08
Может, и вправду, для суммы размеров найти труднее, чем для рюкзака.
Тогда пособие для студентов МФТИ, там для рюкзака есть схема с масштабированием.
Кузюрин, Фомин
Эффективные алгоритмы и сложность вычислений

Очень советую реашть задачу псевдополиномиальным алгоритмом.
Скажем, дано 90 сек. Даны кусочки: 35, 30, 17, 13, 11.

1) Создаешь массив A[90]

2) Берешь очередное число, скажем 35

3) Помечаешь A[35]=1

4) Берешь следующее число, скажем 30

5) Помечаешь A[30]=1

6) Перебераешь все элементы массива помеченные единицей и помечаешь A[35+30]=1

7) И так далее


Очень эффективный алгоритм, если в твоем наборе кусочков одну и ту же сумму можно набрать множеством способов. В худшем случае получаешь алгоритм полного перебора.

Цитата Swetlana @ 10.08.10, 20:57

Зачем её сводить к более общей задаче, мне не очень понятно.

Проще найти код (да хоть у википедиков). Прочём переборные коды весьма компактны... и повыкидывать из них всё лишнее.

Благодаря топикстартёру пишу (для себя, конечно ) набор суммы дин. программированием. Почти дописала.

Почему я так бьюсь за то, что нужно решать не как рюкзак. Если веса отдельных элементов и, соответственно B очень большие, то для такой задачи нужна PTAS - полиномиальная апроксимационная схема. У которой чем меньше погрешность, тем больше время. А у суммы и рюкзака питасы разные, у суммы для той же точности она побыстрее будет.

Цитата Swetlana @ 11.08.10, 05:06

у суммы и рюкзака питасы разные, у суммы для той же точности она побыстрее будет.

ИМХО если чистка кода для рюкзака выполнена верно и полностью - он просто обязан превратиться в код для суммы.

Готово дело
Тестовый пример топикстартёра. Набираем вес 90, но в ответе ближайшая сумма - 89.
Немного переделала прожку из Котова "Лекции по динамическому программированию".

const N=5;
Ves=90;
var
M: array[1..N]of integer;
T:array[0..N,0..Ves]of byte;
sum,i,j:integer;
begin
M[1]:= 35; M[2]:= 30; M[3]:= 17; M[4]:= 13;
M[5]:= 11;
T[0,0] := 1;
for j := 1 to Ves do T[0, j] := 0;
for i := 1 to  N do T[i, 0] := 1;
 
for i := 1 to N do begin
  for j := 1 to Ves do begin
    if j >= M[i] then begin
      if  T[i - 1, j]> T[i - 1, j - M[i]] then
         T[i,j]:= T[i - 1, j]
      else T[i, j]:= T[i - 1, j - M[i]];end
    else T[i, j]:= T[i - 1, j];
  end;
end;
 
for j:=Ves downto 1 do
begin
  sum:=j;
  if T[N, j] = 1 then
    begin
      for i := N downto 1 do
        begin
          if T[i, sum] = T[i - 1, sum] then
            writeln (i, '---No')
          else begin writeln (i, '---Yes');
                     sum := sum - M[i];
               end;
        end;
      break;  
    end;
end;
 
readln;
end.

Сообщение отредактировано: Swetlana - 14.08.11, 17:20

Вот лекции Котова, стр.17, пример №1 "Имеется 5 неделимых предметов..."

Прикреплённый файлЛекции_Котова_по_ДП.doc (596 Кбайт, скачиваний: 3941)

Там есть опечатка, на стр.17
Написано

Цитата

T(i,0)=0 при i≥1. {всегда можно набрать нулевую массу}

А должно быть
T(i,0)=1 при i≥1. {всегда можно набрать нулевую массу}

И, соответственно, в коде нужно исправить

Цитата

for i := 1 to 5 do T[i, 0] := 0;

на
for i := 1 to 5 do T[i, 0] := 1;

Сообщение отредактировано: Swetlana - 17.08.11, 06:54

Спасибо огромнейшее, Светлана, за алгоритм! Вот только если в массиве есть одинаковые числа, он не работает... Может подскажете выход?