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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Несколько вопросов по извучению C++ http://www.cyberforum.ru/cpp-beginners/thread20411.html
Добрый день, товарищи!! Я немного новичек в вопросах программирования на C++, поэтому прошу строго не судить меня за мои, возможно, странные вопросы. Сам я работаю web-разработчиком -...
C++ Задачи с массивами (Ошибка) Ребят, учусь на первом курсе, экзамен по программированию..задача на массивы двумерном массиве 8х10 поменять местами левую верхнюю четверть и правую нижнюю четверть #include <iostream.h> int... http://www.cyberforum.ru/cpp-beginners/thread20398.html
C++ найти простые числа
:wall:Нужно написать програмку, которая выводит на экран простые числа от 1 до 10000, не используя массивы. Я запуталась. Простые, это те которые делятся на 1 и на само себя.
C++ Строковые переменные
Подскажите, какой строковый тип данных поддерживает следующие действия: необходимо ввести с клавиатуры строку, содержащую слова, пробелы, знаки припинания и.т.д. При вводе в одномерный массив char,...
C++ Определить наибольшую последовательность отличных от пробелов символов http://www.cyberforum.ru/cpp-beginners/thread20366.html
Помоги если рубишь на си Помогите после завтра олимпиада по программированию у меня олимпиада а я не как не могу решить эти две задачи: http://www.dstu.edu.ru/informatics/o...l_p3.html#r4_2...
C++ ошибки в С/С++ У меня такой вопрос: существуют ли темы по обсуждению ошибок, есть ли какой-нибудь файл с описанием той или иной ошибки??? СПС за внимание:scratch: подробнее

Показать сообщение отдельно
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
07.01.2009, 23:07
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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.