С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/22: Рейтинг темы: голосов - 22, средняя оценка - 4.82
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16

Жадный алгоритм

13.12.2010, 08:31. Показов 4485. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно правильное. Кто знает? вот вполне рабочий код с жадным алгоритмом.
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
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
int max(double* m, int n) {
  double max;
  int i, k;
  max = m[0];
  for (i=1;i<n;i++)
    if (max < *(m+i)){
      max = *(m+i);
      k = i;
    }
  return k;
}
 
int main() {
  double b = 0;
  cout << "Введите время срочного выполнения: ";
  cin >> b;
 
  int n = 0;
  cout << "Количество заказов: ";
  cin >> n;
 
  double m[n];
  double min_el, min_r, temp, sum, time;
  int mk[n];
  int i, j, k;
  double a[] = {8, 3, 7, 5, 9, 4};
  double c[] = {12, 10, 8, 9, 16, 20};
  // формирование массива отношений времени к прибыли
  for(i=0;i<n;i++) {
    m[i] = a[i] / c[i];
  }
 
 min_el = 0;
  for(j=0;j<n;j++) {
    min_r = m[max(m, n)] - min_el;
    for(i=0;i<n;i++){
      temp = m[i] - min_el;
      if((temp > 0) && (min_r >= temp)) {
        min_r = temp;
        k = i;
      }
    }
    mk[j] = k;
    min_el = m[k];
  }
 
  // подсчёт и вывод результатов
  sum = 0;
  time = 0;
  cout << endl;
  cout << "Выполняйте заказы с номерами:";
  for(i=0;i<n;i++) {
    if((time + a[mk[i]]) <= b) {
      cout << " " << mk[i] + 1;
      time += a[mk[i]];
      sum += c[mk[i]];
    }
  }
  cout << endl;
  cout << "Прибыль: " << sum << endl;
  cout << "Время: " << time << endl;
  return 0;
 
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
13.12.2010, 08:31
Ответы с готовыми решениями:

Жадный алгоритм
Суть задачи - имеется N предметов различного размера. Один ящик имеет строгую вместимость. Необходимо разложить все N предметов в...

жадный алгоритм
написать программу для жадного алгоритма, если не сложно с комментариями в действиях

Жадный алгоритм
Задача: По следам олимпиады. Известно, что оптимальным выбором лыж является такой, когда длина лыж максимально приближена к высоте...

2
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
14.12.2010, 12:28  [ТС]
Выводит ошибку сегментирования, если берешь небольшие массивы, из двух-трех элементов. помогите разобраться?
0
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 7
18.03.2012, 16:56
Выложите пожалуйста полный код на С++ жадного алгоритма...очень надо(
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
18.03.2012, 16:56
Помогаю со студенческими работами здесь

Жадный алгоритм С++
С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну операцию объединяются 2 счета и банк...

Жадный алгоритм
Добрый день. Помогите, пожалуйста, понять, где затаилась ошибка. Это задачка на жадный алгоритм: пользователь вводит размер...

Жадный алгоритм на графе
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть, дан ориентированный взвешенный граф...

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

Жадный граф/алгоритм
Требуется написать программу с графическим интерфейсом: пользователь задаёт точки (A, B, C и т.д.). Далее соединяет между собой какие-то...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru