2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
1

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

13.12.2010, 08:31. Показов 4011. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.12.2010, 08:31
Ответы с готовыми решениями:

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

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

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

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

2
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
14.12.2010, 12:28  [ТС] 2
Выводит ошибку сегментирования, если берешь небольшие массивы, из двух-трех элементов. помогите разобраться?
0
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 7
18.03.2012, 16:56 3
Выложите пожалуйста полный код на С++ жадного алгоритма...очень надо(
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.03.2012, 16:56
Помогаю со студенческими работами здесь

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

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

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

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

Жадный алгоритм сортировки массива(динамический)
Здравствуйте, учусь работать с сортировками массивов, в данном случае жадный алгоритм. Алгоритм...

Жадный алгоритм. Оптимальный состав груза специй
Добрый вечер, можете подсказать как в данной задачи использовать Жадный алгоритм? Капитан...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru