Форум программистов, компьютерный форум CyberForum.ru

Объяснить алгоритм просто перебора - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Sanekz
0 / 0 / 0
Регистрация: 03.01.2013
Сообщений: 24
03.01.2013, 13:40     Объяснить алгоритм просто перебора #1
доброго времени суток! мой вопрос, наверное, покажется Вам очень глупым, но очень нужна ваша помощь!
задачка не сложная:У Вас есть N камней с массами W1, W2 , … WN. Требуется разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.Вводим N, затем N-элементов!(н<18) поэтому пройдет перебор или нет?!
не могли бы Вы написать и объяснить алгоритм перебора или какой-либо другой алгоритм! (язык с++)
Заранее Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.01.2013, 13:40     Объяснить алгоритм просто перебора
Посмотрите здесь:

Алгоритм перебора C++
Задача перебора элементов C++
C++ просто объяснить программу.
C++ Объяснить программу (Алгоритм планирования, Планировщик)
Объяснить алгоритм работы программы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
03.01.2013, 16:02     Объяснить алгоритм просто перебора #2
я могу конечно ошибатся, но можно попробовать её так решить - вводим массив значений масс камней, сортируем по возрастанию и рассматриваем 2 случая:
1)Кол-во камней чётное - ложим в первую кучу первый и последний элемент массива, во вторую кучу второй и предпоследний, снова в первую кучу 3 элем массива и пред пред последний, снова во вторую кучу 4 элемент массива и пред пред пред последний и тд до исчерпания массива.
2)Кол-во камней нечётное - самый первый элемент не трогаем, начиная со второго до последнего делаем пункт номер 1), а потом к куче, в которой получилась меньшая масса, ложим оставшийся 1 камень.

Мне почему-то такое решение сразу в голову пришло.Но говорю сразу - оно может быть и неверно.
0x10
2426 / 1598 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
03.01.2013, 16:33     Объяснить алгоритм просто перебора #3
ZaMaZaN4iK, и сразу же контрпример:
Массы: 1 1 1 1 1 1 1 7.
Если я все правильно понял, по Вашему алгоритму решение будет такое:
- 1 7 1 1
- 1 1 1 1
Разность - (10 - 4) = 6
В то время как оптимальное решение:
- 7
- 1 1 1 1 1 1
Разность: 7 - 7 = 0.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
03.01.2013, 16:38     Объяснить алгоритм просто перебора #4
0x10, ой, точно.Прсто не совсем внимательно прочитал условие.Я почему то подумал, что кол-во камней должно быть либо равное, либо отличатся на единицу.Надо вниматель нее условие читать.Спасибо.
lemegeton
 Аватар для lemegeton
2911 / 1340 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
04.01.2013, 02:09     Объяснить алгоритм просто перебора #5
В лоб такие вещи решаются, конечно, но при количестве элементов массива большем, скажем, 12, ждать станет неприлично долго.

Концепт "в лоб" заключается в том, чтобы перебирая все возможные варианты находить оптимальный.
Пруф ов концепт.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <numeric>
 
struct RandomGenerator {
  int operator()() const { return 1 + ((rand() % 5) ? rand() % 7 : 100 + rand() % 50); }
};
 
template<class Iterator>
double getBestSplitSize(Iterator begin, Iterator end) {
  double result = 0;
  while (begin != end) {
    result += *begin++;
  }
  return result / 2.0;
}
 
template <class Iterator>
Iterator getBestResult(Iterator begin, Iterator end, double ideal) {
  double result = 0.0;
  while (result + *begin < ideal || fabs(result + *begin - ideal) < 0.001) {
    result += *begin++;
  }
  return begin;  
}
 
int main(int argc, char *argv[]) {
  srand(time(0));
 
  int size = 12;
  int *stones = new int[size];
  
  std::generate(stones, stones + size, RandomGenerator());
  std::copy(stones, stones + size, std::ostream_iterator<int>(std::cout, " "));
  std::sort(stones, stones + size);
  std::cout << std::endl;
 
  double idealResult = getBestSplitSize(stones, stones + size);
  std::cout << "Ideal is " << idealResult << "." << std::endl;
 
  int *result = new int[size];
  int bestResult = 0;
  do {
    int thisResult = std::accumulate(stones, getBestResult(stones, stones + size, idealResult), 0);
    if (fabs(thisResult - idealResult) < fabs(bestResult - idealResult)) {
      bestResult = thisResult;
      std::copy(stones, stones + size, result);
    }
  } while (std::next_permutation(stones, stones + size));
  
  int *position = getBestResult(result, result + size, idealResult);
  std::copy(result, position, std::ostream_iterator<int>(std::cout, " "));
  std::cout << "= " << std::accumulate(result, position, 0) << std::endl;
  std::copy(position, result + size, std::ostream_iterator<int>(std::cout, " "));
  std::cout << "= " << std::accumulate(position, result + size, 0) << std::endl;
 
  delete [] result;
  delete [] stones;
 
  std::cin.peek();
  return 0;
}
suff1x
15 / 15 / 1
Регистрация: 26.09.2012
Сообщений: 70
04.01.2013, 03:32     Объяснить алгоритм просто перебора #6
посидел, придумал алгоритм (сразу с примером):

1. упорядочим любой исходный массив W по возрастанию (например получили, W = {1,1,2,3,3,3,4,8,9} )
2. создаем две накопительные переменные Wa, Wb (в них будем просчитывать суммы) и два массива heapA, heapB (тут будут номера камней).
3. в переменную Wa вносим значение W[N-2], Wb - значение W[N-1] (8 и 9 соответственно).
4. в массивы вносим позиции самых "тяжелых" значений heapA[0] = N-2, heapB[0] = N-1.
5. проходим for'ом со счетчиком позиции i по массиву W = {1,1,2,3,3,3,4,8,9} начиная с N-3 до 0:
- сравниваем Wa и Wb (т.е. в нашем примере 8 и 9)
- к меньшей либо равной суммовой переменной плюсуем значение W[i] (т.е. Wa+=4 в нашем примере для первой итерации).
- соответственно в массив heapA[N-i-2] (для позиционированния в массивах heap можно добавить предварительно еще переменные-инкременты - тут уже по желанию) вносим значение i (т.е. номер данного камня, который в кучу А в нашем случае попал).
6. получили два массива с номерами камней - по этим номерам можно определить веса камней по кучам и их перечислить итогом по группам.

ниже пару примеров вкратце обрисую итеративно (-1 в "кучковых" массивах - предварительно занесем в качестве признака отсутствия камня - это для примера, массивы эти правильней сделать динамическими естественно):

пример 1 (чуть подробнее):
позиция: 0,1,2,3,4,5,6,7,8
значение: 1,1,2,3,3,3,4,8,9
N = 9;

i=6) 8<9 -> Wa=8+4=12;Wb=9; heapA{7;6;-1;-1;-1;-1;-1;-1};heapB{8;-1;-1;-1;-1;-1;-1;-1}
i=5) 12>9 -> Wa=12;Wb=9+3=12; heapA{7;6;-1;-1;-1;-1;-1;-1};heapB{8;-1;5;-1;-1;-1;-1;-1}
i=4) 12=12 -> Wa=12+3=15;Wb=12; heapA{7;6;-1;4;-1;-1;-1;-1};heapB{8;-1;5;-1;-1;-1;-1;-1}
i=3) 15>12 -> Wa=15;Wb=12+3=15; heapA{7;6;-1;4;-1;-1;-1;-1};heapB{8;-1;5;-1;3;-1;-1;-1}
i=2) 15=15 -> Wa=15+2=17;Wb=15; heapA{7;6;-1;4;-1;2;-1;-1};heapB{8;-1;5;-1;3;-1;-1;-1}
i=1) 17>15 -> Wa=17;Wb=15+1=16; heapA{7;6;-1;4;-1;2;-1;-1};heapB{8;-1;5;-1;3;-1;1;-1}
i=0) 17>16 -> Wa=17;Wb=16+1=17; heapA{7;6;-1;4;-1;2;-1;-1};heapB{8;-1;5;-1;3;-1;1;0}

из полученных массивов heap соберем веса кучек:
куча А = 8+4+3+2 = 17
куча B = 9+3+3+1+1 = 17

пример 2 (сокращенно, думаю понятно будет):
позиция: 0,1,2,3,4,5,6,7
значение: 1,1,1,1,1,1,1,7

1,1,1,1,1,1,1,7
1,1,1,1,1,2,7
1,1,1,1,3,7
1,1,1,4,7
1,1,5,7
1,6,7
7,7

пример 3:

значение: 1,2,2,2,6,6,9,11

1,2,2,2,6,6,9,11
1,2,2,2,6,15,11
1,2,2,2,15,17
1,2,2,17,17
1,2,19,17
1,19,19
20,19

и т.п.

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

ps. автору темы спасибо за простую, но интересную задачку.
pps. в предыдущий код lemegeton'а не втыкал - возможно там тоже самое.
Valli1
4 / 4 / 0
Регистрация: 14.09.2012
Сообщений: 64
04.01.2013, 18:32     Объяснить алгоритм просто перебора #7
Добавлено через 10 часов 23 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
 
{int m []= {5,6,7,8,0,0,0,0};
int total=0;
int i; int j; int h; int z;
for(int i=0;i<5;i++)
total+=m[i]/2;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
for(h=0;h<8;h++)
for(z=0;z<8;z++)
if (i!=j&&i!=h&&i!=z&&j!=h&&j!=z&&z&&h!=z){
if(m[i]+m[j]+m[h]+m[z]==total)
std::cout<<m[i]<<" "<<m[j]<<" "<<m[h]<<" "<<m[z]<<'\n';
if ((m[i]+m[j]+m[h]+m[z]>total)&&((m[i]+m[j]+m[h]+m[z]-total)<5))//5 минимальное значение массива, нули добавить.
std::cout<<m[i]<<" "<<m[j]<<" "<<m[h]<<" "<<m[z]<<'\n';}
 
std::cin.get();
std::cin.get();
 
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2013, 00:01     Объяснить алгоритм просто перебора
Еще ссылки по теме:

Кто может объяснить алгоритм прораммы.Как она работает? C++
Кто может объяснить алгоритм программы? Как она работает? C++
Алгоритм перебора цифр 0 и 1 в четырехзначном числе C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
LiveRos
62 / 67 / 1
Регистрация: 05.10.2012
Сообщений: 240
06.01.2013, 00:01     Объяснить алгоритм просто перебора #8
Как насчет такого:
массив камней: 3,5,7,8,11,2,9
узнать сумму всех элементов массива - 45
делим на 2 (у нас же 2 кучки будет?) - 22,5
сортируем камни по весу 2,3,5,7,8,9,11
начинаем собирать кучки
первая кучка не должна быть тяжелее 22,5
сравнили самый тяжелый элемент с первой кучкой, не больше? (22,5>11) - берем
следующий элемент - 9, 11+9=20<22.5 - берем 9
следующий - 8, 20+8=28>22.5 - не берем
следующий - 7, 20+7=27>22.5 - не берем
следующий - 5, 20+5=25>22.5 - не берем
следующий - 3, 20+3=23>22.5 - не берем
следующий - 2, 20+2=22<22.5 - берем
массив закончился.
Все остальное сбрасываем в кучку 2.
Надеюсь понятно
Yandex
Объявления
06.01.2013, 00:01     Объяснить алгоритм просто перебора
Ответ Создать тему
Опции темы

Текущее время: 16:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru