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

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

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

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

07.01.2009, 15:30. Просмотров 2289. Ответов 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 т.

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

В массив, упорядоченный по убыванию значений элементов, добавить новое число так, чтобы не нарушить упорядоченность - C++
Имеется задача. В массив Х(N), N≤20, упорядоченный по убыванию значений элементов, добавить новое число так, чтобы не нарушить...

Сформировать массив,так чтобы элементы заштрихованной области были равны 1,а остальные 0 - C++
Сформировать массив,так чтобы элементы заштрихованной области были равны 1, а остальные 0.

Отсортировать двумерный массив так, чтобы максимальные и минимальные значения строк были упорядочены - C++
Привет всем нуждаюсь в помощи с задачей по С++. Она выглядит так: Дан двумерный массив. Разместить его строки так, чтобы при их просмотре...

Упорядочить массив так, чтобы вначале были элементы встречающиеся более одного раза - C++
Условие: есть неупорядоченный массив, нужно упорядочить его таки образом, чтобы вначале были элементы встречающиеся более одного раза. ...

Изменить заданный числовой массив так, чтобы элементы были расположены в нем в обратном порядке - C++
Доброго времени суток. Изменить заданный числовой массив так, чтобы элементы были расположены в нем в обратном порядке. Задача...

Переставить строки матрицы так, чтобы суммы элементов строк были расположены в порядке их возрастания - C++
Задать двумерный массив размерами m и n. Обработать массив согласно заданию, вывести на печать исходный и обработанный массивы....

17
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 1
07.01.2009, 16:46 #2
Позновато спохватился... ничего стопроцентного пока в голову не лезет
0
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 16:49  [ТС] #3
Цитата Сообщение от Sinys Посмотреть сообщение
Позновато спохватился... ничего стопроцентного пока в голову не лезет
Хай Вы подумайте плиииз.... Можно и чтоб решалось 50-70% тестов
0
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 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];
};
только надо массив отсортировать по возростанию
0
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, извини я дочитал от радости..... мне сначала его отсортировать надо потом в цикл???
0
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 1
07.01.2009, 17:59 #6
Да сначала сортировку потом етот цикл пример проходит (в теории)
0
GalaX
697 / 569 / 21
Регистрация: 18.11.2008
Сообщений: 2,153
07.01.2009, 17:59 #7
Цитата Сообщение от Jamshed Посмотреть сообщение
мне сначала его отсортировать надо потом в цикл???
да
0
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 Посмотреть сообщение
Да сначала сортировку потом етот цикл пример проходит (в теории)
Ну что просмотрел, братан....
0
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 1
07.01.2009, 19:50 #9
Мде у меня даже не компилится...
Походу у тебя с сортировкой что то не то... без сортировки будет выводить 44 и 49..
0
Jamshed
0 / 0 / 0
Регистрация: 06.01.2009
Сообщений: 18
07.01.2009, 20:15  [ТС] #10
Цитата Сообщение от Sinys Посмотреть сообщение
Мде у меня даже не компилится...
Походу у тебя с сортировкой что то не то... без сортировки будет выводить 44 и 49..
Нет без сортировки 39 40...
0
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 1
07.01.2009, 20:26 #11
Ты в моем алгоритме ошибку зделал в 24й строке:
s=n/2

Добавлено через 2 минуты 17 секунд
Блин ошибка s=n-1
0
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, и все таки ошибочно
0
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 1
07.01.2009, 21:09 #13
Хз алгоритм я написал должен работать...
Смысл алгоритма: берем в 1ю стопку 1е и последнее число, во 2ю стопку второе и предпоследнее. потом к той стопке которая меньше добавляем наибольшее оставшееся число а к большей - меньшее.
0
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;
       }
0
Sinys
27 / 27 / 2
Регистрация: 25.12.2008
Сообщений: 185
Завершенные тесты: 1
07.01.2009, 23:11 #15
Общий вес будет 40, значит на две группы приходится по 20.
Я думал на ету тему но как реализовать не придумал
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2009, 23:11
Привет! Вот еще темы с ответами:

В каждом столбце обнулите минимальное количество элементов так, чтобы сумма элементов столбца не превышала заданную - C++
Помогите решить при помощи функций.плиссзО_о Пусть дана матрица А(n x m), состоящая из натуральных чисел. В каждом столбце обнулите...

слить массив А и В по 100 элементов в массив С из 200 элементов так,чтобы элементы А и В чередовались по 10 в c++ - C++
слить массив А и В по 100 элементов в массив С из 200 элементов так,чтобы элементы А и В чередовались по 10 в c++

Вывести на экран m первых элементов последовательности так, чтобы их сумма оказалась меньше 1000 - C++
Вывести на экран m первых (a1, a2, …) элементов последовательности an=2+2n², так, чтобы их сумма оказалась меньше 1000, а сумма m+1 первых...

Слить массивы А и В по 100 элементов в массив С из 200 элементов так,чтобы элементы А и В чередовались по 10 - C++
слить массив А и В по 100 элементов в массив С из 200 элементов так,чтобы элементы А и В чередовались по 10


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
07.01.2009, 23:11
Ответ Создать тему
Опции темы

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