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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
АлександрШ
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
13.12.2010, 08:31     Жадный алгоритм #1
Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно правильное. Кто знает? вот вполне рабочий код с жадным алгоритмом.
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;
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2010, 08:31     Жадный алгоритм
Посмотрите здесь:

C++ Алгоритм
Волновой алгоритм (алгоритм Ли) C++
Жадный алгоритм для определения последовательности обхода городов. C++
C++ Жадный алгоритм
Помогите алгоритм для char переделать в алгоритм для float C++
C++ Жадный алгоритм на графе
Жадный граф/алгоритм C++
C++ Жадный алгоритм С++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
АлександрШ
 Аватар для АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
14.12.2010, 12:28  [ТС]     Жадный алгоритм #2
Выводит ошибку сегментирования, если берешь небольшие массивы, из двух-трех элементов. помогите разобраться?
светлана1990
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 7
18.03.2012, 16:56     Жадный алгоритм #3
Выложите пожалуйста полный код на С++ жадного алгоритма...очень надо(
Yandex
Объявления
18.03.2012, 16:56     Жадный алгоритм
Ответ Создать тему
Опции темы

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