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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
#1

Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки - C++

07.01.2009, 15:30. Просмотров 2198. Ответов 17
Метки нет (Все метки)

Здравствуйте!!! Помогите мне ... У меня ЗАВТРА экзамен....

В морском порту города Владивостока хранятся N контейнеров (N - чётное число). Для погрузки контейнеров на судно, чтобы обеспечить равномерную загрузку, их необходимо разделить на две половины так, чтобы их массы были максимально близки. Решить эту задачу, предполагая, что информация о массах контейнеров (в тоннах) хранится в массиве M(N). В качестве ответа указать номера контейнеров одной половины и получаемые массы для каждой из половин.
Например:
Если M(6)=(10, 15, 18, 20, 16, 14), то одну половину составят 1, 4, 5 контейнеры (другую 2, 3, 6). Масса первой группы m1=10+20+16=46 т., масса второй группы m2=15+18+14=47 т.

ВХОДНЫЕ ДАННЫЕ ВВОДЯТСЯ НЕ С ФАЙЛА, а просто с КЛАВИАТУРЫ!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2009, 15:30     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки
Посмотрите здесь:

В каждом столбце обнулите минимальное количество элементов так, чтобы сумма элементов столбца не превышала заданную C++
C++ Упорядочить массив так, чтобы вначале были элементы встречающиеся более одного раза
Вывести на экран m первых элементов последовательности так, чтобы их сумма оказалась меньше 1000 C++
C++ слить массив А и В по 100 элементов в массив С из 200 элементов так,чтобы элементы А и В чередовались по 10 в c++
C++ Слить массивы А и В по 100 элементов в массив С из 200 элементов так,чтобы элементы А и В чередовались по 10
C++ Как сделать так, чтобы функции были не вложенными?
В массив, упорядоченный по убыванию значений элементов, добавить новое число так, чтобы не нарушить упорядоченность C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 16:46     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #2
Позновато спохватился... ничего стопроцентного пока в голову не лезет
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 16:49  [ТС]     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #3
Цитата Сообщение от Sinys Посмотреть сообщение
Позновато спохватился... ничего стопроцентного пока в голову не лезет
Хай Вы подумайте плиииз.... Можно и чтоб решалось 50-70% тестов
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 17:24     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
int mas[n];
int a,b;
i=0;
j=n-1;
a=mas[i]+mas[j];
b=mas[i++]+mas[j--];
for (i=1 && j=n-2; i<n/2 && j>n/2; i++ && j--)
{
if (a<b)
 a+=mas[j] && b+=mas[i];
else a+=mas[i]  b+=mas[j];
};
только надо массив отсортировать по возростанию
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 17:53  [ТС]     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #5
Спасибо братан.... Но алгоритм этот даже и тест, который в примере не проходит...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<string.h>
main(){
       int n;
       scanf ("%i",&n);
       int i=0,j=n-1,k,mas[n],a,b,s,m;
       for (k=0; k<n; k++){
           scanf ("%i",&mas[k]);
           }
       a=mas[i]+mas[j];
       b=mas[i++]+mas[j--];
       s=n-2;m=n/2;
       for (i=1,j=s; m>i,m<j; i++,j--)
       {
           if (a<b){a+=mas[j]; b+=mas[i];}
           else {a+=mas[i];  b+=mas[j];}
           };
       printf ("%i %i",a,b);
       getchar();
       getchar();
       return 0;
       }
Добавлено через 1 минуту 53 секунды
Sinys, извини я дочитал от радости..... мне сначала его отсортировать надо потом в цикл???
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 17:59     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #6
Да сначала сортировку потом етот цикл пример проходит (в теории)
GalaX
696 / 568 / 21
Регистрация: 18.11.2008
Сообщений: 2,152
07.01.2009, 17:59     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #7
Цитата Сообщение от Jamshed Посмотреть сообщение
мне сначала его отсортировать надо потом в цикл???
да
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 19:17  [ТС]     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #8
Цитата Сообщение от Sinys Посмотреть сообщение
Да сначала сортировку потом етот цикл пример проходит (в теории)
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
#include<stdio.h>
#include<string.h>
void sort(int a[],int n){
     int i,j,tmp=0;
for (i=0; i<n-1; i++) {
  for (j=0; j<n-1-i; j++)
    if (a[j+1] < a[j]) {  
      tmp = a[j];         
      a[j] = a[j+1];
      a[j+1] = tmp;
  }
}
}
main(){
       int n;
       scanf ("%i",&n);
       int i=0,j=n-1,k,mas[n],a=0,b=0,s,m;
       for (k=0; k<n; k++){
           scanf ("%i",&mas[k]);
           }
           sort(mas,n);
       a+=mas[i]+mas[j];
       b+=mas[i++]+mas[j--];
       s=n-2;m=n/2;
       for (i=1,j=s; m>i,m<j; i++,j--)
       {
           if (a<b){a+=mas[j]; b+=mas[i];}
           else {a+=mas[i];  b+=mas[j];}
           };
       printf ("%i %i",a,b);
       getchar();
       getchar();
       return 0;
       }
Synsis, ну кась ты проверь братан теперь при вводе 10 15 18 20 16 14, выводит 44 и 48, а должен 46 и 47

Добавлено через 29 минут 14 секунд
Цитата Сообщение от Sinys Посмотреть сообщение
Да сначала сортировку потом етот цикл пример проходит (в теории)
Ну что просмотрел, братан....
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 19:50     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #9
Мде у меня даже не компилится...
Походу у тебя с сортировкой что то не то... без сортировки будет выводить 44 и 49..
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 20:15  [ТС]     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #10
Цитата Сообщение от Sinys Посмотреть сообщение
Мде у меня даже не компилится...
Походу у тебя с сортировкой что то не то... без сортировки будет выводить 44 и 49..
Нет без сортировки 39 40...
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 20:26     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #11
Ты в моем алгоритме ошибку зделал в 24й строке:
s=n/2

Добавлено через 2 минуты 17 секунд
Блин ошибка s=n-1
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 20:52  [ТС]     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #12
Цитата Сообщение от Sinys Посмотреть сообщение
Ты в моем алгоритме ошибку зделал в 24й строке:
s=n/2

Добавлено через 2 минуты 17 секунд
Блин ошибка s=n-1
и все таки ошибочно

Добавлено через 6 минут 15 секунд
Sinys, и все таки ошибочно
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 21:09     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #13
Хз алгоритм я написал должен работать...
Смысл алгоритма: берем в 1ю стопку 1е и последнее число, во 2ю стопку второе и предпоследнее. потом к той стопке которая меньше добавляем наибольшее оставшееся число а к большей - меньшее.
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
07.01.2009, 23:07     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #14
Sinys, у меня кстати тоже не работает этот алгоритм!!!

Добавлено через 4 минуты 22 секунды
Я по-своему алгоритму написал, работает 100%.

Суть в том, что не обязательно должны получиться две группы одинакового размера: В одной группе может быть один контейнер, во второй все остальные. Например контейнеры с массой {1,10,4,3,20,2}. Общий вес будет 40, значит на две группы приходится по 20.

Вот полная программа:
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
#include<stdio.h>
#include <conio.h>
 
void sort(int a[],int n)
{
for (int i=0; i<n-1; i++)
  for (int j=0; j<n-1-i; j++)
    if (a[j] < a[j+1])
      {
         int tmp = a[j];
         a[j] = a[j+1];
         a[j+1] = tmp;
 
         tmp = a[j+n];
         a[j+n] = a[j+1+n];
         a[j+1+n] = tmp;
      }
}
 
int main()
{
 
int n,sum=0;
printf("Vvedite kolichestvo konteinerov: ");
scanf ("%i",&n);
 
int *mas = new int[n+n];
int *out = new int[n];
 
    // загрузка данных
    printf("Vvedite massu konteinerov:\n");
    for (int k=0,i=n,j=0; k<n; k++,i++,j++)
        {
          scanf ("%i",&mas[k]);
          mas[i]=i-n+1;
          sum+=mas[k];
          out[j]=0;
        }
    sort(mas,n);
 
    int s=mas[0];
    out[0]=mas[0];
 
    // отбор элементов по весу
    for (int k=1; k < n; k++)
    {
      if (mas[n-1]+s<=sum/2)
       {
        for (int i=k; i<n; i++)
          if (mas[i]+s<=sum/2)
            {
              s+=mas[i];
              out[i]=mas[i];
              break;
            }
        }
      else
        {
         if (s==sum/2) break;
         s-=mas[k-1];
         out[k-1]=0;
         k--;
        }
    }
 
    // вывод результатов на экран
    printf ("\nGruppa1\n");
    for (int k=0,s=0; k<n; k++)
      if (out[k]!=0) printf ("#%i - %i\n",mas[k+n],out[k]);
    printf ("Obwii ves gruppu - %i\n",s);
 
    s=0;
    printf ("\nGruppa2\n");
    for (int k=0; k<n; k++)
      if (out[k]==0)
      {
       printf ("#%d - %d\n",mas[k+n],mas[k]);
       s+=mas[k];
      }
    printf ("Obwii ves gruppu - %i\n",s);
   // конец вывода результатов на экран
 
   getch();
   delete[] mas;
   delete[] out;
   return 0;
       }
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
07.01.2009, 23:11     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #15
Общий вес будет 40, значит на две группы приходится по 20.
Я думал на ету тему но как реализовать не придумал
bmw666
9 / 7 / 1
Регистрация: 25.12.2008
Сообщений: 40
08.01.2009, 06:10     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #16
Вот собственно все 100% работает
только я применил матричный массив ибо надо запоминать и положение/номер груза
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 <conio.h>
#include <iostream.h>
#define N 10
 
int main()
{
    int M[N][2], x=1, a=0, b=0;
    for(int j=0; j<N; j++)
    {
        cin >> M[j][0];
        M[j][1]=j;
    }
    while(x)
    {
        x=0;
        for(int i=0; i<N-1; i++)
            if(M[i][0]<M[i+1][0])
            {
                int Nbuff, buff;
                buff=M[i][0];
                Nbuff=M[i][1];
                M[i][0]=M[i+1][0];
                M[i][1]=M[i+1][1];
                M[i+1][0]=buff;
                M[i+1][1]=Nbuff;
                x=1;
            }
    }
    cout << "A(No->Ves)\tB(No->Ves)" << endl;
    for(int k=0; k<N; k++)
    {
        if(a>b)
        {
            b+=M[k][0];
            cout << "\t\t" << M[k][1]+1 << "->" << M[k][0] << endl;
        }
        else
        {
            a+=M[k][0];
            cout << M[k][1]+1 << "->" << M[k][0] << endl;
        }
    }
    cout << "A=" << a << "\nB=" << b << endl;
    getch();
}
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
08.01.2009, 12:45     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #17
В принципе предыдущая программа тоже запоминала положение груза.

Добавлено через 6 минут 6 секунд
Цитата Сообщение от bmw666 Посмотреть сообщение
Вот собственно все 100% работает
Странно! я ввел значение #define N 6, после чего заполнил массив значениями 10 15 18 20 16 14, как в примере, так сумма получилась 45 и 48...

Зачем ломать голову, если программу уже написали???
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2009, 17:47     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки
Еще ссылки по теме:

Изменить заданный числовой массив так, чтобы элементы были расположены в нем в обратном порядке C++
C++ Отсортировать строки массива так, чтобы первой шла строка, сумма элементов которой была меньше, чем остальных
C++ Сформировать массив,так чтобы элементы заштрихованной области были равны 1,а остальные 0
Переставить строки матрицы так, чтобы суммы элементов строк были расположены в порядке их возрастания C++
Отсортировать двумерный массив так, чтобы максимальные и минимальные значения строк были упорядочены C++

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

Или воспользуйтесь поиском по форуму:
Sinys
26 / 26 / 2
Регистрация: 25.12.2008
Сообщений: 177
Завершенные тесты: 1
08.01.2009, 17:47     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки #18
Странно! я ввел значение #define N 6, после чего заполнил массив значениями 10 15 18 20 16 14, как в примере, так сумма получилась 45 и 48...

Зачем ломать голову, если программу уже написали???
Ради интереса...
Yandex
Объявления
08.01.2009, 17:47     Разделить массив на две половины так, чтобы сумма значений элементов были максимально близки
Ответ Создать тему
Опции темы

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