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

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

27.04.2016, 13:34. Показов 2379. Ответов 8
Метки нет (Все метки)

Задача:
По следам олимпиады. Известно, что оптимальным выбором лыж является такой, когда длина лыж максимально приближена к высоте спортсмена. Команда состоит из n спортсменов, чей рост составляет h1, h2, … , hn. На команду выдан комплект n пар лыж длиной l1, l2, … , ln. Необходимо реализовать алгоритм выдачи лыж спортсменам, который бы обеспечивал минимум суммы абсолютной разности между ростом спортсмена и парой лыж, доставшейся ему.

Подскажите хотя бы, с чего начать, откуда танцевать, так сказать. Слабо понимаю алгоритм.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.04.2016, 13:34
Ответы с готовыми решениями:

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

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

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

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

8
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
27.04.2016, 13:39 2
насколько я себе представляю жадность - оптимальные локальные решения на каждом шаге.
идешь циклом по всем спортсменам и выбираешь каждому лучший вариант из того, что осталось. жадное решение может быть не точным.
0
68 / 67 / 59
Регистрация: 14.07.2013
Сообщений: 251
27.04.2016, 14:02 3
Да еще вопрос.
Допустим рост лыжников 180 180 и 150. Лыжи 180 180 190.
Что надо 180-180 180-180 150-190 или 180-180 180-190 150-180
И так и так суммарная разница 40, но во втором случае минимизирован максимум
0
0 / 0 / 0
Регистрация: 05.03.2014
Сообщений: 32
27.04.2016, 14:03  [ТС] 4
В данной задаче это без разницы. То есть как получается работает алгоритм? Идем в цикле по спортсменам и подбираем для него лучшую длину лыж и так далее?
0
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
27.04.2016, 14:17 5
akaAxeL, ну это показывает неэффективность жадного алгоритма для данной задачи, типа "последовательность локально оптимальных выборов не даёт глобально оптимальное решение". мы не про эффективность наверное - на то он и жадный, чтобы каждый жадно хватал те лыжи, которые ему больше подходят, не думая, что оденут другие.
0
0 / 0 / 0
Регистрация: 05.03.2014
Сообщений: 32
27.04.2016, 14:25  [ТС] 6
А такой вопрос. Как исключить спортсменов и выбранные ими лыжи из массива? Чтобы повторно не проходить по использованным лыжам в цикле?
0
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
27.04.2016, 14:32 7
hiddenofheaven, как вариант можно создать булевский массив длины n, инициализировать его истиной и выключать ячейки, соответствующие занятым лыжам.
0
0 / 0 / 0
Регистрация: 05.03.2014
Сообщений: 32
27.04.2016, 17:15  [ТС] 8
Не поможете с кодом реализации? Хотя бы наброски, дальше сам раскручу)
0
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
27.04.2016, 18:17 9
hiddenofheaven, на коленке набросал
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
#include <iostream>
using namespace std;
 
const size_t N = 3;
 
unsigned men[] = { 180, 180, 150 };
unsigned ski[] = { 180, 190, 180 };
 
static inline unsigned myabs(int t)
{
    return (t < 0) ? -t : t;
}
 
int main()
{
    bool available[N];
    // everyone is available
    for (size_t i = 0; i < N; ++i)
        available[i] = true;
    size_t answer[N] = { 0 };
 
    for (size_t i = 0; i < N; ++i)
    {
        size_t best = N + 1; // impossible value
        unsigned delta = 0;
        for (size_t j = 0; j < N; ++j)
        {
            if (available[j])
            {
                if (best == N + 1)
                {
                    best = j;
                    delta = myabs(men[i] - ski[best]);
                }
                else
                {
                    if (myabs(men[i] - ski[j]) < delta)
                    {
                        best = j;
                        delta = myabs(men[i] - ski[best]);
                    }
                }
            }
        }
        answer[i] = best;
        available[best] = false;
    }
    for (size_t i = 0; i < N; ++i)
        cout << "man #" << i << " with height " << men[i] << " took " << ski[answer[i]] << "\n";
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.04.2016, 18:17
Помогаю со студенческими работами здесь

Жадный алгоритм
Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно...

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

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

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


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

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

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