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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
alibaba314
18 / 18 / 1
Регистрация: 22.03.2009
Сообщений: 58
#1

минимальное подмножество отрезков - C++

17.10.2009, 12:23. Просмотров 1382. Ответов 10
Метки нет (Все метки)

всем привет!

помогите мне решить одну задачу:

написать программу. которая для множества заданных отрезков находит минимальное подмножество отрезков. объединение которых покрывает отрезок S=[0,10000]. число отрезков и координаты их концов заданы на входе. Все координаты целочисленные.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2009, 12:23     минимальное подмножество отрезков
Посмотрите здесь:

C++ найти в массиве наибольшее подмножество...
C++ Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой
C++ Поиск отрезков
C++ Пересечение отрезков
Дерево отрезков C++
Найти максимальное по числу вершин подмножество C++
C++ На прямой своими концами заданы N отрезков. Найти точку принадлежащую максимальному числу отрезков
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
17.10.2009, 12:34     минимальное подмножество отрезков #2
ну так ты начни, хотя бы ввод данных сделай. ошибки поправим, алгоритм обсудим
alibaba314
18 / 18 / 1
Регистрация: 22.03.2009
Сообщений: 58
17.10.2009, 13:44  [ТС]     минимальное подмножество отрезков #3
вот алгоритм:

покрывайте отрезок S пошагово. двигаясь слева направо. на каждом шаге будет непокрытая часть [x, 10000] . из оставшихся отрезков выбирайте тот, который урежет непокрытую часть до [y, 10000], где "y" максимальное.
kravam
быдлокодер
1695 / 874 / 44
Регистрация: 04.06.2008
Сообщений: 5,338
17.10.2009, 13:58     минимальное подмножество отрезков #4
Приехали.
Во-первых, надо найти длины всех отрезков
(Например: 34, 567, 21, 457, 432, 45, 543, 10,)

Во-вторых, их надо отсортировать по убыванию
(567, 543, 457, 432, 45, 34, 21, 10)

А потом начинай с самого левого члена этой последовательности и сравнивай его с 10000. Если он меньше, то прибавляй следующий член, сумму снова сравнивай с 10000. Одновременно инкременируй счётчик отрезков

Как только сумма станет больше или равной 10000, значит ты нашёл искомые отрезки. Величина счётчика и есть их минимальное число.
Привет.
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
17.10.2009, 16:12     минимальное подмножество отрезков #5
пробуем, тестим.
ввод через фаил (в файле только пары (начало и конец) отрезков)
ввод организовал как мне удобно, а не по условию
на вывод отладки можно не заморачиваться, главное это результат
а промежуточный вывод для удобства

const int begDiapason = 0;
const int endDiapason = 100; - границы диапазона

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
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define sizeVec(c) int((c).size())
#define all(c) (c).begin(),(c).end()
 
#define LENGTH(a)  ((*a).first) 
#define BEG(a)  ((*a).second.first) 
#define END(a)  ((*a).second.second)        
 
const int begDiapason = 0;
const int endDiapason = 100;
 
typedef  vector<pair< int, pair<int, int> > > SEGMENT;
int main()
{
    char *file="data.txt";
    int beg, end, counter=0;
    bool flag;
    SEGMENT arrSeg;
    SEGMENT::iterator itt;
 
    ifstream f(file);
    if (!(f.is_open()))  // проверка наличия первого файла с текстом
        cout<<"ERROR: not file "<<file;
    else
        while(!f.eof()) // чтении из файла
        {   
            f>>beg; f>>end;
            arrSeg.push_back(make_pair(end-beg, make_pair(beg, end)));
        }
 
 
    // вывод для отладки
    for (SEGMENT::iterator it=arrSeg.begin(); it<arrSeg.end(); it++)
        cout<<"length:"<<LENGTH(it)<<" beg:"<<BEG(it)<<" end:"<<END(it)<<endl;
    cout<<endl;
 
//  sort(all(arrSeg));  reverse(all(arrSeg));  // можно иначе
 
    beg=begDiapason; 
//  for (itt=arrSeg.begin(); itt<arrSeg.end(); itt++)
//     if (beg>=BEG(itt)) 
//      { beg=END(itt); break; }
// 
//  if(beg!=begDiapason) // если после первого поиска не обнаружен отрезок с begDiapason..Х
//  {
//      cout<<++counter<<". length:"<<LENGTH(itt)<<" beg:"<<BEG(itt)<<" end:"<<END(itt)<<endl;
//      arrSeg.erase(itt);
        
        while (!(arrSeg.empty()))
        {
            // достигли конца диапазона
            if (beg>=endDiapason) break;
            // подравниваем все отрезки под текущую позицию бегунка
            for (SEGMENT::iterator it=arrSeg.begin(); it<arrSeg.end(); it++)
                if (beg>BEG(it))    
                    { BEG(it)=beg; LENGTH(it)=END(it)-BEG(it); }
      // сортируем по убыванию (полезные длины отрезков поменялись)
            sort(all(arrSeg));  reverse(all(arrSeg)); 
 
            // ищем максимальный отрезок начинающийся с позиции бегунка
            flag=false;
            for (itt=arrSeg.begin(); itt<arrSeg.end(); itt++)
                if (beg>=BEG(itt)) 
                { flag=true; break; }
 
            if (flag==false) break;
            // если бегунок на отрезке длиной больше нуля
            // инкрементируем счётчик отрезков и по новой
            if (LENGTH(itt)>0)
            {
                cout<<++counter
                    <<". length:"<<LENGTH(itt)
                    <<" beg:"<<BEG(itt)
                    <<" end:"<<END(itt)<<endl;
                beg=END(itt);
                arrSeg.erase(itt);
            }
            else
                break;
        }
        
        if(beg>=endDiapason)
            cout<<"\nmin number segments: "<<counter;
        else
            cout<<"\nit cannot be done: ";
 
    f.close();  cout << endl;   system("PAUSE");
    return 0;
}
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
17.10.2009, 22:37     минимальное подмножество отрезков #6
Как только сумма станет больше или равной 10000, значит ты нашёл искомые отрезки. Величина счётчика и есть их минимальное число.
2kramav: прочитай внимательно условие задачи.

Добавлено через 2 минуты
Если перебирать тупо, то будет очень много вариантов: 2^N, где N - число отрезков.
А вообще эта задача решается методом динамического программирования.
TanT уже должен сообразить как
TanT
эволюционирую потихоньку
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
17.10.2009, 22:43     минимальное подмножество отрезков #7
Цитата Сообщение от odip Посмотреть сообщение
TanT уже должен сообразить как
odip, мой код выше. но я не совсем уверен, что это о чём вы мне говорили на другой ветки.
как не прискорбно мне это принимать, но я не совсем понял/оценил предложенный вами вариант.
предлагаю попробовать снова осветить вопрос динамического программирования, что, несомненно, будет полезно всем остальным участникам или прям, не стеснясь, вот так ссылкой на источник отправить меня учить мат.часть.
я даже не обижусь.
kravam
быдлокодер
1695 / 874 / 44
Регистрация: 04.06.2008
Сообщений: 5,338
17.10.2009, 23:14     минимальное подмножество отрезков #8
Цитата Сообщение от odip Посмотреть сообщение
2kramav: прочитай внимательно условие задачи.

Добавлено через 2 минуты
Если перебирать тупо, то будет очень много вариантов: 2^N, где N - число отрезков.
А вообще эта задача решается методом динамического программирования.
TanT уже должен сообразить как
А что его читать?
Там вызывает непонимание такая фраза:
"объединение которых покрывает отрезок S=[0,10000]"

Ну, я предположил что речь идёт о

""Сумма длин которых покрывает отрезок S=[0,10000]"
Ну то есть сумма длин которых превышает 10000.

Вот и складываю помаленечку себе.
Теперь о "тупо перебирать"

Не знаю, где Вы увидели два в энной степени, но не у меня, факт.
Мой вариант предполагает n вариантов.
То есть если отрезков 10, то 10 длин рассматриваем и всё. А не 2 в степени 10
Естественно, отсортировав прежде массив этих самых длин.

Задекларирую свой способ как оптимальный.
Кто может предложить лучше- пусть предложит. Только чур, умных рож не делать и пыль в глаза не пускать и завесу из слов непонятных не создавать.
Говорить чисто и честно, дабы дурь каждого была видна, как говорил Пётр Первый.
Короче, Пафнутий, не говори красиво.

На крайняк голимый код.
Но с комментариями.
Привет.
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
18.10.2009, 19:14     минимальное подмножество отрезков #9
2kravam:
В условии написано: "число отрезков и координаты их концов заданы на входе".
Если нужна только длина отрезков, то зачем еще координаты концов ?
И зачем тогда указывать что покрыть нужно именно от 0 до 10000 ?
Ты неправильно понял задачу.
Нужно покрывать отрезками, но сами отрезки сдвигать никуда нельзя.
Если отрезок от 100 до 200, то это значит что он покрывает от 100 до 200 и в другое место его не сдвинуть.
Задекларирую свой способ как оптимальный.
Декларируй. Только ты решаешь совсем не ту задачу.
kravam
быдлокодер
1695 / 874 / 44
Регистрация: 04.06.2008
Сообщений: 5,338
18.10.2009, 21:09     минимальное подмножество отрезков #10
Я ничё не понял.
Меня термин покрыть добивает. Не знаю, что он обозначает.
Пусть автор сам решает такие задачи.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2009, 12:09     минимальное подмножество отрезков
Еще ссылки по теме:

Найти подмножество множества C++
Найти путь, соединяющий вершины a и b и не проходящий через заданное подмножество вершин V C++
Из заданного множества int чисел определить максимальное подмножество C++
C++ Есть ли у кого похожий алгоритм: распределения отрезков разной длины внутри отрезков фиксированной длины?

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

Или воспользуйтесь поиском по форуму:
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
19.10.2009, 12:09     минимальное подмножество отрезков #11
Покрыть - это значит накрыть каждую точку диапазона своим отрезком сверху.
Но отрезки можно класть только на те позиции которые указаны для них.
То есть сдвигать отрезок влево или вправо нельзя.
Yandex
Объявления
19.10.2009, 12:09     минимальное подмножество отрезков
Ответ Создать тему
Опции темы

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