Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.03.2010, 18:45
гость

 
Сообщений: n/a

Равные суммы
Имеется два множества чисел (a_i) и (b_i) (чисел в каждом множесте меньше 100 и они не превосходят 1000).... нужно найти сколько различных чисел можно представить в виде суммы некоторых элементов множества А, так и в виде суммы некоторых элементов множества В..

Время 0,1 с !!!

Единственная идея которая приходит в голову.. это рассмотреть все числа от 1 до 100000 и проверить можно ли их представить в виде суммы из множества А и В.. но это врядли войдёт во время..
  #2  
Старый 16.03.2010, 19:14
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

c помощью динамического программирования можно найти, какие числа из диапазона 100000 представимы в виде суммы элементов множества
Идея такая - завести массив [0..MaxSum], нулевой элемент инициализировать единицей, остальные нулем.
Затем для каждого элемента множества Ak пробегаем по массиву, и если в i-й ячейке единица, то ставим единицу и в i+Ak ячейку
  #3  
Старый 17.03.2010, 00:14
гость

 
Сообщений: n/a

а
но ведь алгоритм будет учитывать и суммы, в которых элемент из одного множества будет учитываться несколько раз..
вот вроде как нашёл неплохой алгоритм http://www.cs.berkeley.edu/~luca/w42...ts/notesdp.pdf
  #4  
Старый 17.03.2010, 08:27
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

да, subset sum можно использовать.
А вот набросок (особо не тестировал) того, что я написал:
Код:
  SetLength(B, Sum + 1);
  B[0] := 1;
  for i := 0 to High(A) do begin
    for j := 0 to Sum - A[i] do
      if (B[j] = 1) and (B[j + A[i]] = 0) then
        B[j + A[i]] := -1;
    for j := 1 to Sum do
      if B[j] = -1 then
        B[j] := 1;
  end;

Последний раз редактировалось MBo, 17.03.2010 в 16:29.
  #5  
Старый 18.03.2010, 08:02
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

а так вообще кратенько получается, без второго обхода с зачисткой:
Код:
  for i := 0 to High(A) do begin
    for j := 0 to Sum - A[i] do
      if (DWord(B[j] - 1) <= i) and (B[j + A[i]] = 0) then  
     //эквивалентно if (B[j] > 0) and (B[j] <= i + 1) and (B[j + A[i]] = 0)
        B[j + A[i]] := i + 2;
  end;

Последний раз редактировалось MBo, 18.03.2010 в 08:04.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пожалуйста, помогите (алгоритм набора суммы) гость Графы 0 23.12.2009 12:14
Агоритм выделение суммы полных квадратов Jim Математические алгоритмы 4 19.10.2009 00:09
Строки неодинаковых чисел постоянной суммы konstantin Оффтопик 18 11.06.2009 11:25
Как разрезать пластину на две равные части. гость Вычислительная геометрия 0 28.07.2008 17:31
Корень из суммы квадратов Michael_K Математические алгоритмы (другое) 19 15.04.2008 01:07