VPF::[C/C++] Найти в массиве набор элементов!

Kiryousha

Дата 26.1.2009, 12:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 26.1.2009

Репутация: нет
Всего: нет

Всем здравствуйте!
Срочно необходима помощь в решении следующей задачи:
из заданного массива целых чисел выбрать набор, сумма элементов которого будет наиболее близка к заданному числу. Вывести на экран найденные элементы и полученную сумму.
Заранее спасибо!

Strell

Дата 26.1.2009, 13:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 16
Регистрация: 7.12.2006

Репутация: нет
Всего: 1

Можно реализовать с рекурсией, можно без. решай сам.

Вот набросал пример с рекурсией.

Ну а на следующий раз - в центр помощи!!!! smile

Код


#include <iostream.h>
#include <math.h>
#include <conio.h>


int inline getValuesSumm(int *mass, int fromValue, int valuesCount)
    {
        int res = 0;
      for (int i=fromValue; i<fromValue + valuesCount; i++)
       {
                res += mass[i];
         }
      return res;

   }


int findMaxMatch(int * mass, int massLength, int needValue, int &fromValue, int &valuesCount)
    {
        int from = fromValue;
        int count = valuesCount;
      int nextFrom = 0;
      int nextCount = 0;
      int minCount = 1;
      int minSumm = abs(needValue -  mass[fromValue]);
      int summ = 0;
      for (int i=2; i<massLength - fromValue; i++)
       {
                summ = getValuesSumm(mass, fromValue, i);
            if (abs(needValue - summ) < minSumm)
             {
                minSumm = abs(needValue - summ);
                  minCount = i;
               }
         }

      if (fromValue + 1 < massLength)
       {
            nextFrom = fromValue + 1;
          summ = findMaxMatch(mass, massLength, needValue, nextFrom, nextCount);
            if (summ < minSumm)
             {
                fromValue = nextFrom;
                  valuesCount = nextCount;
               } else
               {
                        valuesCount = minCount;
               }
            return summ < minSumm?summ:minSumm;
         }
      valuesCount = minCount;
      return minSumm;


   }


void main(void)
{
    int mass[] = {0, 5, 6, 8, 2, 1, 3, 4,4, 0, 3, 3, 1};
   int needValue = 13;
   int fromValue = 0;
   int valuesCount = 0;

    int minSumm = findMaxMatch(mass, 13, needValue, fromValue, valuesCount);

   cout << "\r\nMin match value: " << minSumm << " massive elements: \r\n[";
   for (int i=fromValue; i<fromValue + valuesCount; i++)
    cout << (i==fromValue?"":", ")<<mass[i];
   cout <<"]\r\n";
   getch();
}

Kiryousha

Дата 26.1.2009, 15:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 26.1.2009

Репутация: нет
Всего: нет

Спасибо большое за оперативную помощь! Хулиганить больше не буду! smile

P.S. Кстати, я девушка! smile

Это сообщение отредактировал(а) Kiryousha - 26.1.2009, 15:27

Kiryousha

Дата 26.1.2009, 18:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 26.1.2009

Репутация: нет
Всего: нет

Ознакомилась с данным алгоритмом более подробно. Он не отрабатывает, к примеру, следующую ситуацию:
есть массив, отсортированый по убыванию {11,7,5,3}. Ищу набор элементов, наиболее близкий к 19. Резульат получаю [11,7], хотя более правильным будет [11,5,3].
Есть предложение сделать так: в отсортированном по убыванию массиве, первый элемент поочерёдно сложить с последующими элементами массива. Получим новую последовательность. Для приведённого выше примера - {18,16,14}. Сравнивая с искомым числом каждый элемент, видим, что предел поиска ещё не достигнут, тогда к новой полученной последовательности начинаем прибавлять минимальное значение из последовательности, в нашем случае 3. Получаем {21,19,17}. Что и требовалось найти.
В общем случае:
Если бы на данном шаге мы получили значение разности между искомым числом и элементом массива большее, чем разность, найденную в предыдущей последовательности, то, как результат, взяли бы соответственно меньшее из них.
Если бы на данном шаге не достигли наилучшего результата, то продолжали прибавлять минимальные элементы.

Может не самый красивый алгоритм, но походит для любых последовательностей.
Проблема в том, как его реализовать.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »