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

Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.76
tpoiiia
0 / 0 / 0
Регистрация: 20.04.2012
Сообщений: 3
22.04.2012, 10:38     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #1
Здравствуйте, помогите, пожалуйста, решить данную ниже задачу.

У Вас есть N камней с массами W1, W2 , … WN. Требуется разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.
Входные данные

В первой строке входного файла INPUT.TXT записано число N – количество камней (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы камней W1, W2 , … WN (1 ≤ Wi ≤ 105).
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух кучек.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2012, 10:38     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.
Посмотрите здесь:

C++ Как сделать так, чтобы программа не компилилась, хотя синтаксически была бы правильной?
рабочая программа. но нужно ее переписать так, чтобы она была наиболее общей. C++
C++ Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
Массив: Образовать новую последовательность чисел так, чтобы она тоже была неубывающей C++
C++ В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 12:11     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #2
примени динамическое программирование. главное полный перебор не делай - он не оптимален.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 12:26     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #3
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
главное полный перебор не делай - он не оптимален.
В данном случае это не правда. При таких ограничениях:
Цитата Сообщение от tpoiiia Посмотреть сообщение
N – количество камней (1 ≤ N ≤ 18).
полный перебор займет меньше секунды.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 13:14     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #4
тебе при полном переборе предстоит перебрать 2^18 вариантов
или 262144, для каждого найти вес И того
262144*18=4718592 действий это минимум
если на нахождение одного варианта у тебя одна операция тратится
пять миллионов меньше чем за секунду?

Добавлено через 16 минут
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
int solve(int* a, int N){
int s=0;
int i;
for (i=0; i<N; i++)
 s+=a[i];
int* t1, t2, t3;
int sz=s/2+s%2;
int* t1=new int[sz+1];
int* t2=new int[sz+1];
for (i=0; i<sz; i++)
{
    t1[sz]=0; t2[sz]=0;
}
for (i=0; i<N; i++){
 for (j=0; j<=sz; j++){
    if (j-a[i]>=0){
         t2[j]=max(t1[j], t1[j-a[i]]+a[i]);
       }
       else
         t2[j]=t1[j];
  }
t3=t2;
t2=t1;
t1=t3;
}
delete[] t1;
delete[] t2;
 
 
int a, dsz, c;
a=s-t2[sz];
if (a>t2[sz]) dsz=a-t2[sz];
else dsz=t2[sz]-a;
a=s-t2[sz-1];
if (a>t2[sz-1]) c=a-t2[sz];
else c=t2[sz]-a;
 
if (dsz<c) return dsz;
else return c 
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 13:35     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
тебе при полном переборе предстоит перебрать 2^18 вариантов
или 262144, для каждого найти вес И того
262144*18=4718592 действий это минимум
если на нахождение одного варианта у тебя одна операция тратится
пять миллионов меньше чем за секунду?
Kuzia domovenok, у Вас очень плохо с математикой. Вот код:
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
#include <stdio.h>
#include <math.h>
int res, N, mas[18];
void rec(int n, int sum1, int sum2)
{
    if(n==N)
    {
        if(abs(sum1-sum2)<res)
            res=abs(sum1-sum2);
        return;
    }
    rec(n+1, sum1+mas[n], sum2);
    rec(n+1, sum1, sum2+mas[n]);
}
int main()
{
      freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
    res=2000000;
    int i;
    scanf("%d", &N);
    for(i=0; i<N; i++)
        scanf("%d", &mas[i]);
    rec(0,0,0);
    printf("%d\n", res);
 
return 0;
}
в котором реализован полный перебор. Всего действий (+ или -) в нем 2^18=262144 вариантов. Еще столько же вариантов (если често то в два раза больше, но можно написать код чтобы было столько же) - это сравнение полученного результата с имеющимся. Ни о каких
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
4718592 действий
речь не идет.
Чтобы не быть голословным я нашел эту задачу. Она здесь:
http://********/?main=task&id_task=71
Мой код прошел все тесты и показал: 0,197 секунды.
Итог: все-таки с математикой Вы не сильно дружите ).
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 13:47     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #6
ну вот, я тебе и написал 262144, прочесть не смог?
рекурсия запросто увеличит это число в несколько раз

У тебя алгоритм экспоненциальной сложности,
а у меня порядка N*N*Wсред
Максимум 34000 действий, и то, если все без исключения камни по 108 весят
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 14:04     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ну вот, я тебе и написал 262144, прочесть не смог?
смог, но еще смог прочитать:
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
262144*18=4718592 действий это минимум
если на нахождение одного варианта у тебя одна операция тратится
пять миллионов меньше чем за секунду?
Насчет ДП против ничего не имею, кстати первый раз сдавал эту задачу именно с помощью ДП. Но в данном случае опровергаю выдвинную Вами "теорию":
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
главное полный перебор не делай - он не оптимален.

Не по теме:

А Вы сами пробовали Ваш код сдавать по указанной ссылке?

tpoiiia
0 / 0 / 0
Регистрация: 20.04.2012
Сообщений: 3
22.04.2012, 14:34  [ТС]     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #8
valeriikozlov, спасибо большое за код.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 14:41     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А Вы сами пробовали Ваш код сдавать по указанной ссылке?
смотрел ссылку, ничего не понял. Это какой-то задачник по программированию?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 14:51     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #10
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
смотрел ссылку, ничего не понял. Это какой-то задачник по программированию?
Это система онлайн проверки решений олимпиадных задач. Если есть желание, то начинайте отсюда:
http://********/
здесь регистрируйтесь и обязательно прочитайте раздел "новичкам".
thick_int
Заблокирован
22.04.2012, 15:51     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #11
А что делать будете, если камней будет не 18, а скажем 10000?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 20:25     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #12
Цитата Сообщение от thick_int Посмотреть сообщение
А что делать будете, если камней будет не 18, а скажем 10000?
Решать.

thick_int, Вы просто теорию хотите узнать или есть задача, на эту же тему, только с ограничениями N до 10000? Если есть такая задача, то давайте ссылку на нее.
thick_int
Заблокирован
23.04.2012, 03:14     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #13
Ну вообще-то про теорию решения подобных задач.
Мне вот так кажется, что исходная задача сводится к задаче нахождения кортежа, такого что, разница между суммой элементов которого и половиной суммарной массы, минимальна.
djkah11
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 5
03.07.2012, 00:12     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #14
Решал задачу сам, вот сделал такое решение.
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
#include <iostream>
 
 
using namespace std;
 
int main()
{
int a,t;
cin>>a;
int b[19];
for (int i=0;i<a;i++) {cin>>b[i];}
if (a!=1) {
for (int y=0;y<a;y++){
    for (int h=y+1;h<a;h++) {
        if (b[y]>b[h])
         {t=b[y];
         b[y]=b[h];
         b[h]=t;
         }
         }
         }
 
 int s1=b[a-1];
 
 int s2=b[a-2];
  
 int k=a-3;
 
  while (k>(-1)) {
        if (s1>s2) { s2+=b[k];} else {s1+=b[k];}
        
        k--;
}
 
int u=s1-s2;
if (u>0) {cout<<u;} else {cout<<-u;};}
 
      else {cout<<b[0];};
         
 
 
 
 
    return 0;
}
Подскажите плз в чем ошибка, вроде сам тестил - все работает.
P.s. решал задачу с другим условием у меня кол-во камней от 1 до 20.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,689
03.07.2012, 00:21     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #15
напишите алгоритм для дп пожалуйста)
djkah11
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 5
03.07.2012, 00:42     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #16
1)сортируем массив по возрастанию
2)кидаем в первую кучу самый тяжелый камень, во вторую 2ой с конца.
потом идем с конца, докидываем во 2-ю кучу камней, пока она не станет больше первой, после этого докидываем в первую кучу камней пока она не станет больше второй и т. д.
Но, увы, он не работает почему-то.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.08.2012, 02:23     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.
Еще ссылки по теме:

Разложить число в массив так, чтобы элементами была последовательность с единицы о этого числа C++
C++ Как обратиться к объекту bitset так, чтобы результатом была битовая маска
Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным C++

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

Или воспользуйтесь поиском по форуму:
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
06.08.2012, 02:23     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. #17
Попоробовал решать эту задачу. Вот примерная схема алгоритма:

Предположим, что нам дан массив вещественных чисел, значения которых представляют веса камней из рассматриваемой основной кучи. Прежде всего, отсортируем данный массив, который впредь мы будем рассматривать как сортированный. Если куча содержит два или три камня, то тогда решение задачи тривиально: во вторую кучу кладем самый тяжелый камень, а в первую кучу складываем все остальные камни. Всюду далее будем считать, что камней, как минимум 4.

Далее найдем суммарный вес камней, а с ней и половину веса всех камней.

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

Теперь несколько забежим вперед и рассмотрим какой-нибудь конкретный расклад камней по кучам. Такой расклад характеризуется камнями, которые находятся в первой куче, во второй куче и камнями, которые еще не разложены. Сейчас наша задача будет состоять в том, чтобы выявить среди неразложенных камней те из них, которые заведомо должны быть либо в первой куче, либо во второй куче. Хотя, вполне вероятно, что ни одного из таких камней мы не найдем.

Сперва рассмотрим вторую кучу. Вопрос с первой кучей решается аналогично. Будем среди неразложенных камней искать те из них, которые обладают следующими свойствами: 1) сумма весов данного камня и суммарного веса камней, которые уже положены во вторую кучу больше половины суммарного веса всех камней, 2) среди неразложенных камней есть камни меньшего веса, удовлетворяющие данному условию. В этом случае каждый такой камень должен быть помещен в первую кучу. Оставшиеся неразложенные камни обработаем подобным образом на предмет выявления среди них тех, которые заведомо должны попадать уже во вторую кучу.

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

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

Очевидно, что подобная схема носит рекурсивный характер. Поэтому, чтобы снизить рекурсивную нагрузку мы поступим следующим образом. Данный алгоритм будет продолжаться до тех пор, пока мы либо не найдем такой расклад, при котором суммарный вес камней в одной из двух куч будет равен половине суммарного веса всех камней, либо до тех пор, пока количество еще неразложенных камней не станет равным 3. В этом последнем случае, мы будем тупо ручным способом будем искать наилучший расклад, не забывая, конечно, о том, что при нахождении такого расклада, при котором суммарный вес камней в одной из двух куч равный половину суммарного веса всех камней является наилучшим результатом, после чего все действующие на данный момент цепочки раскладывания должны быть прекращены.

Добавлено через 1 час 57 минут
Теперь приведу код

Заголовочный файл: heaps.h:

#pragma once
#include <vector>

using namespace std;

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class heaps
{
public:
    heaps(double *, int);
    ~heaps();
    static void print();
private:
    heaps(vector<double> *, vector<double> *, vector<double> *);
    static bool goldHit;
    static double bestDiff;
    static double halfWeight;
    static vector<double> bestFirstHeap;
    static vector<double> bestSecondHeap;
    vector<double> * restHeapPtr;
    vector<double> * firstHeapPtr;
    vector<double> * secondHeapPtr;
    void firstPart();
    void secondPart();
    void initiate();
};
Реализация: Файл heaps.cpp (очень длинный)

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
#include "stdafx.h"
 
#include <iostream>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iterator>
#include <numeric>
 
#include "Heaps.h"
 
bool heaps::goldHit = false;
double heaps::bestDiff = 0.0;
double heaps::halfWeight = 0.0;
vector<double> heaps::bestFirstHeap = vector<double>();
vector<double> heaps::bestSecondHeap = vector<double>();
 
heaps::heaps(double * stoneArray, int arrSize)
{
    sort(stoneArray, stoneArray + arrSize);
    halfWeight = accumulate(stoneArray, stoneArray + arrSize, 0.0) / 2.0;
    restHeapPtr = new vector<double>(stoneArray, stoneArray + arrSize);
    firstHeapPtr = new vector<double>();
    secondHeapPtr = new vector<double>();
    secondHeapPtr->push_back(restHeapPtr->back());
    restHeapPtr->pop_back();
    bestFirstHeap = *restHeapPtr;
    bestSecondHeap = *secondHeapPtr;
    if (bestSecondHeap.back() == halfWeight)
        goldHit = true;
    else
    {
        bestDiff = fabs(accumulate(bestFirstHeap.begin(), bestFirstHeap.end(), 0.0) - accumulate(bestSecondHeap.begin(), bestSecondHeap.end(), 0.0));
        initiate();
    }
}
 
heaps::heaps(vector<double> * rest, vector<double> * first, vector<double> * second)
{
    restHeapPtr = new vector<double>(*rest);
    firstHeapPtr = new vector<double>(*first);
    secondHeapPtr = new vector<double>(*second);
}
 
heaps::~heaps()
{
    delete secondHeapPtr;
    secondHeapPtr = nullptr;
    delete firstHeapPtr;
    firstHeapPtr = nullptr;
    delete restHeapPtr;
    restHeapPtr = nullptr;
}
 
void heaps::firstPart()
{
    if (goldHit)
        return;
    assert(restHeapPtr->size() > 3);
    bool heapsStateChanged = true;
    bool firstHeapChanged = false;
    bool secondHeapChanged = false;
    double weight1 = accumulate(firstHeapPtr->begin(), firstHeapPtr->end(), 0.0);
    
    double weight2 = accumulate(secondHeapPtr->begin(), secondHeapPtr->end(), 0.0);
    vector<double>::const_iterator pos;
    do
    {
        for (pos = restHeapPtr->cbegin(); pos != restHeapPtr->cend(); ++pos)
        {
            if (*pos + weight2 == halfWeight)
            {
                goldHit = true;
                secondHeapPtr->push_back(*pos);
                restHeapPtr->erase(pos);
                copy(restHeapPtr->cbegin(), restHeapPtr->cend(), back_inserter(*firstHeapPtr));
                bestFirstHeap = *firstHeapPtr;
                bestSecondHeap = *secondHeapPtr;
                bestDiff = 0;
                delete this;
                return;
            }
            else if (*pos + weight2 > halfWeight)
                break;
        }
        if (pos != restHeapPtr->cend() && ++pos != restHeapPtr->cend())
        {
            copy(pos, restHeapPtr->cend(), back_inserter(*secondHeapPtr));
            restHeapPtr->erase(pos, restHeapPtr->cend());
            firstHeapChanged = true;
            if (restHeapPtr->size() <= 3)
            {
                while (restHeapPtr->size() != 3)
                {
                    restHeapPtr->push_back(secondHeapPtr->back());
                    secondHeapPtr->pop_back();
                }
                secondPart();
                return;
            }
        }
        else
            firstHeapChanged = false;
        for (pos = restHeapPtr->cbegin(); pos != restHeapPtr->cend(); ++pos)
        {
            if (*pos + weight1 == halfWeight)
            {
                goldHit = true;
                firstHeapPtr->push_back(*pos);
                restHeapPtr->erase(pos);
                copy(restHeapPtr->cbegin(), restHeapPtr->cend(), back_inserter(*secondHeapPtr));
                bestFirstHeap = *firstHeapPtr;
                bestSecondHeap = *secondHeapPtr;
                bestDiff = 0;
                delete this;
                return;
            }
            else if (*pos + weight1 > halfWeight)
                break;
        }
        if (pos != restHeapPtr->cend() && ++pos != restHeapPtr->cend())
        {
            copy(pos, restHeapPtr->cend(), back_inserter(*firstHeapPtr));
            restHeapPtr->erase(pos, restHeapPtr->cend());
            secondHeapChanged = true;
            if (restHeapPtr->size() <= 3)
            {
                while (restHeapPtr->size() != 3)
                {
                    restHeapPtr->push_back(firstHeapPtr->back());
                    firstHeapPtr->pop_back();
                }
                secondPart();
                return;
            }
        }
        else
            secondHeapChanged = false;
        heapsStateChanged = firstHeapChanged || secondHeapChanged;
        firstHeapChanged = false;
        secondHeapChanged = false;
    }while (heapsStateChanged);
 
    
    double tempDouble = restHeapPtr->back();
    restHeapPtr->pop_back();
    secondHeapPtr->push_back(tempDouble);
    heaps * tempHeaps1 = new heaps(restHeapPtr, firstHeapPtr, secondHeapPtr);
    secondHeapPtr->pop_back();
    firstHeapPtr->push_back(tempDouble);
    heaps * tempHeaps2 = new heaps(restHeapPtr, firstHeapPtr, secondHeapPtr);
    tempHeaps1->initiate();
    if (goldHit)
        return;
    else
        tempHeaps2->initiate();
    delete this;
}
 
void heaps::secondPart()
{
    if (goldHit)
        return;
    double thisDiff, tempDiff;
    int bestCase;
    assert(restHeapPtr->size() == 3);
    double weight1 = accumulate(firstHeapPtr->begin(), firstHeapPtr->end(), 0.0);
    double weight2 = accumulate(secondHeapPtr->begin(), secondHeapPtr->end(), 0.0);
    bestCase = 1; //первый камень из оставшихся идет в первую кучу
    thisDiff = fabs(weight1 + restHeapPtr->at(0) - weight2 - restHeapPtr->at(1) - restHeapPtr->at(2));
    if (thisDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    tempDiff = fabs(weight1 + restHeapPtr->at(1) - weight2 - restHeapPtr->at(0) - restHeapPtr->at(2));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 2; //второй камень из оставшихся идет в первую кучу
    }
    tempDiff = fabs(weight1 + restHeapPtr->at(2) - weight2 - restHeapPtr->at(0) - restHeapPtr->at(1));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 3; //третий камень из оставшихся идет в первую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(0) - weight1 - restHeapPtr->at(1) - restHeapPtr->at(2));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 4; //первый камень из оставшихся идет во вторую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(1) - weight1 - restHeapPtr->at(0) - restHeapPtr->at(2));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 5; //второй камень из оставшихся идет во вторую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(2) - weight1 - restHeapPtr->at(0) - restHeapPtr->at(1));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 6; //третий камень из оставшихся идет во вторую кучу
    }
    tempDiff = fabs(weight1 + restHeapPtr->at(0) + restHeapPtr->at(1) + restHeapPtr->at(2) - weight2);
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 7; //все оставшиеся камни попадают в первую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(0) + restHeapPtr->at(1) + restHeapPtr->at(2) - weight1);
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 8; //все оставшиеся камни попадают во вторую кучу
    }
    if (thisDiff < bestDiff)
    {
        bestFirstHeap = *firstHeapPtr;
        bestSecondHeap = *secondHeapPtr;
        bestDiff = thisDiff;
        switch (bestCase)
        {
            case 1:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
            case 2:
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
            case 3:
                bestFirstHeap.push_back(restHeapPtr->at(2));
                bestSecondHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                break;
            case 4:
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestFirstHeap.push_back(restHeapPtr->at(2));
                bestSecondHeap.push_back(restHeapPtr->at(0));
                break;
            case 5:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestFirstHeap.push_back(restHeapPtr->at(2));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                break;
            case 6:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
            case 7:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestFirstHeap.push_back(restHeapPtr->at(2));
                break;
            case 8:
                bestSecondHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
        }
    }
    delete this;
}
 
void heaps::initiate()
{
    if (restHeapPtr->size() > 3)
        firstPart();
    else
        secondPart();
}
 
void heaps::print()
{
    sort(bestFirstHeap.begin(), bestFirstHeap.end());
    sort(bestSecondHeap.begin(), bestSecondHeap.end());
    cout << "Best stone distribution is as follows: " << endl;
    cout << "Heap 1: ";
    copy (bestFirstHeap.begin(), bestFirstHeap.end(), ostream_iterator<double>(cout, ", "));
    cout << "\b\b  " << endl;
    cout << "Heap 2: ";
    copy (bestSecondHeap.begin(), bestSecondHeap.end(), ostream_iterator<double>(cout, ", "));
    cout << "\b\b  " << endl;
    cout << "Weights differense is " << bestDiff << endl;
}
И, наконец, главная программа (файл Stones.cpp):

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
#include "stdafx.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <cmath>
 
#include "Heaps.h"
 
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    double stoneArray[] = {21, 2, 7, 4, 7, 3, 3, 10, 10, 18, 19, 10};
    
 
    assert(sizeof(stoneArray) / sizeof(stoneArray[0]) > 1);
    if (sizeof(stoneArray) <= 3) //неинтересный случай, решаемый вручную
    {
        sort(stoneArray, stoneArray + sizeof(stoneArray) / sizeof(stoneArray[0]));
        cout << "Best stone distribution is as follows: " << endl;
        cout << "Heap 1: ";
        copy (stoneArray, stoneArray + sizeof(stoneArray) / sizeof(stoneArray[0]) - 1, ostream_iterator<double>(cout, ", "));
        cout << "\b\b  " << endl;
        cout << "Heap 2: ";
        cout << stoneArray[sizeof(stoneArray) / sizeof(stoneArray[0]) - 1];
        cout << endl;
        cout << "Weights differense is " << fabs(accumulate(stoneArray, stoneArray + sizeof(stoneArray) / sizeof(stoneArray[0]) - 1, 0.0) - stoneArray[sizeof(stoneArray) / sizeof(stoneArray[0]) - 1]) << endl;
    }
    else //а здесь с использованием класса
    {
        heaps * MyHeapsPtr = new heaps(stoneArray, sizeof(stoneArray) / sizeof(stoneArray[0]));
        MyHeapsPtr->print();
        //delete MyHeapsPtr; не требуется ибо удаляется в функции SecondPart()
    }
    cout << endl;
    return 0;
}
Yandex
Объявления
06.08.2012, 02:23     Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.
Ответ Создать тему
Опции темы

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