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

Динамическое программирование - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
08.06.2012, 20:27     Динамическое программирование #1
Есть такая задача:
Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а длина от 1 до 8. В стене может быть дыры, она может состоят из разных частей.

Пример решения взял с задачи про сдачу

Вот мое решение, но оно не всегда выдает правильное решение.
На этом примере работает правильно
6 3
101101
111111
111111
3
1 4
2 6
3 1

а тут нет
8 2
11111111
00000000
3
1 7
3 2
4 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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
// LWP_Test.cpp : Defines the entry point for the console application.
//#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
 
typedef std::map<unsigned int,int> mymap;
typedef std::vector<int> myarr;
 
// Ф-ция считывания исходных данных из файла 
bool readFile(
              const char *str, // Имя файла
              myarr &_arr,     // Массив с кол-вом кирпичей в каждом ряде
              mymap &_map      // Набор блоков
              );
// Ф-ция проверяем может ли быть построена стена из данного набора
// блоков по заданой конструкции
bool verifyWall(
                myarr &_arr, // Массив с кол-вом кирпичей в каждом ряде
                mymap &_map // Набор блоков
                );
// Проверяет и удаляет из набора блоки с нулевым кол-вом
void checkMap(
              mymap &_map // Набор блоков для проверки
              );
 
int main()
{
    mymap _map;
    myarr arr;
    std::string fileName;
 
    std::cout << "Enter file name: ";
    getline( std::cin, fileName );
 
    readFile( fileName.c_str(), arr, _map );
 
    std::cout << ( verifyWall( arr, _map ) ? "Yes" : "No" ) << std::endl;   
 
    system("PAUSE");
    return 0;
}
 
bool readFile( const char *str, myarr &_arr, mymap &_map )
{
    if ( str == NULL )
        return false;
 
    // Отрытие файла
    std::ifstream infile(str);
 
    if ( infile == NULL )
        return false;
 
    // Считывание ширины и высоты стены
    int w, h;
    infile >> w >> h;
    if ( w <= 0 && h <= 0 )
        return false;
 
    // Преобразование схемы стены в количество кирпичей в каждом ряду.
    // При обнаружении дыры в стене,следующая часть ряда считает,
    // как новый ряд для облегчения проверки.
    char tmp;
    int c = 0;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            infile >> tmp;
            if ( tmp - '0' == 1)
            {
                c++;
            } 
            else if ( c > 0 )
            {
                _arr.push_back( c );
                c = 0;
            }
        }
        if ( c > 0 )
            _arr.push_back( c );
        c = 0;
    }
    // Переворачиваем так, чтобы начинать рассматривать с нижнего ряда стены
    reverse( _arr.begin(), _arr.end() );
 
    // считываем кол-во блоков в наборе
    int s;
    infile >> s;
    if ( s <= 0 )
        return false;
 
    // Заносим инфо о блоков в ассоциативный массив
    // Ключ - вид блока(кол-во кирпичей в блоке)
    // Значение - кол-во блоков.
    int n1, n;
    for (int i = 0; i < s; i++)
    {
        infile >> n1 >> n;
        if ( n1 <= 0 && n <= 0 )
            return false;
 
        _map[n1] = n;
    }
 
    return true;
}
 
bool verifyWall( myarr &_arr, mymap &_map )
{
    // Для хранения значения выражения для данного ряда
    // F(n) = min(F(n - a1), F(n - a2),.., F(n - ak)) + 1. 
    myarr F;
 
    const int INF=1000000000; // условно обозначим бесконечност
    for ( unsigned int i = 0, n = 0; i < _arr.size(); i++ )
    {
        // Времменый контейнер для учета кол-ва блоков в наборе
        mymap snd( _map.begin(), _map.end() );
        // Кол-во кирпичей в данном ряде
        n = _arr[i];
        F.resize( n+1 );
        F[0] = 0; 
 
        for( unsigned int j = 1; j <= n; j++ )
        {                    
            F[j] = INF;
            mymap::iterator it = snd.begin();
            // Перебераем весь набор блоков
            while ( it != snd.end() )
            {
                if( j >= it->first && F[j-it->first]+1 < F[j] ) // Ищем лучший способ заполнить ряд
                {
                    F[j] = F[j-it->first]+1;
                    it->second--; // Уменьшаем кол-во блока
                }
                it++;
                // Проверяем, чтобы в набое не было блоков с нулевым кол-вом.
                checkMap(snd);
            }
        }
    
        // F[n] элемент сожержит кол-во блоков, которыми можно построить данный ряд,
        // если значение равно бесконечности, то данный ряд из данного набора блоков 
        // построить нельзя
        if ( F[n] == INF )
            return false;
        else
            while( n > 0 )
            {
                mymap::iterator it = _map.begin();
                while ( it != _map.end() )
                {
                    if ( F[n-it->first] == F[n]-1 ) // Можем строить данным блоком 
                    {
                        n-=it->first; // умельшаем кол-во кирпичей в ряде
                        it->second--; // уменьшаем кол-во используемого блока
                        checkMap( _map );
                        break;
                    }
                    it++;
                }
            }
 
        F.clear();
    }
 
    return true;
}
 
void checkMap( mymap &_map )
{
    mymap::iterator it = _map.begin(), itcur;
    while ( it != _map.end() )
    {
        if ( it->second == 0 )
            _map.erase( it++ );
        else
            it++;
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2012, 20:27     Динамическое программирование
Посмотрите здесь:

C++ динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
10.06.2012, 01:52  [ТС]     Динамическое программирование #2
Up!
Кто-то может подсказать в решении задачи о сдаче?!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.06.2012, 07:52     Динамическое программирование #3
Цитата Сообщение от insolent Посмотреть сообщение
Кто-то может подсказать в решении задачи о сдаче?!
У Вас условие очень скромное (похоже не все написали).
Можно ли кирпичи ставить вертикально?
Максимальный размер массива описывающий стену?
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
10.06.2012, 13:33  [ТС]     Динамическое программирование #4
Кирпиче ставят только горизонтально, размер стены неограниченный, как и конструкция стены.
Все данные считываются с файла:
1) Считываются ширина и высоты стены;
2) Считывается матрица стены: 1 - кирпич, 0 - дыра (себе для облегчения я считаю, что после дыры начинается новый псевдоряд)
3) Считывается количество кирпичей в наборе
4) Считываются кирпичи: первое число - ширина кирпича, второе - кол-во
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.06.2012, 15:28     Динамическое программирование #5
insolent, динамическое программирование в этой задаче не применимо (по крайней мере я точно не вижу как его применить).
Самое сложное в этой задаче попытаюсь объяснить таким примером:
есть набор кирпичей:
4
1 1
2 1
3 1
4 1
В первой строке стены есть 5 подряд идущих единиц. Чтобы бы набрать 5 единиц можно использовать два варианта: (2 и 3) или (1 и 4).
Но в следующей строке может быть: (1 отдельная единица и 4 отдельно подряд идущих единиц) или (2 отдельно подряд идущих единицы и 3 отдельно подряд идущих единицы).
Поэтому выбрав для первой строки какой-то вариант, может не получиться заполнить вторую строку (хотя на самом деле построить такую стену можно).
Я привел маленький пример. Для больших стен будет важно как укладывать кирпичи в каждом ряду. Задача пахнет перебором, а не ДП.
Я вообще переформулировал бы задачу так:
Считаем подряд идущие единицы в каждом ряду и получаем сколько каких рядов нужно набрать. Например для теста:
6 3
101101
111111
111111
Получилось бы так:
1 2// нужно набрать два ряда размером 1
2 1// нужно набрать один ряд размером 2
6 2// нужно набрать два ряда размером 6
Можно ли набрать такие ряды имея такой набор кирпичей:
3
1 4
2 6
3 1
И получается что эта задача имеет мало что общего с задачей про сдачу, а больше похожа на задачу:
http://acm.timus.ru/problem.aspx?space=1&num=1115
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
10.06.2012, 20:02  [ТС]     Динамическое программирование #6
Я использовал ДП из соображения, что каждый ряд нужно построить найменьшим числом кирпичей.
Очень похожа, теперь бы разобраться, как её решить..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.06.2012, 21:29     Динамическое программирование #7
Цитата Сообщение от insolent Посмотреть сообщение
Очень похожа, теперь бы разобраться, как её решить..
Перебором. Но при переборе использовать жадный алгоритм: начинать с заполнения максимальных рядов (максимального количества подряд идущих единиц) и пытаться использовать сначало кирпичи с максимальной длиной.
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
10.06.2012, 23:26  [ТС]     Динамическое программирование #8
valeriikozlov, спасибо за помощь буду пробовать решить. Я первоначально хотел решать жадным алгоритмом, но чего-то решил делать с помощью метода ДП
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
13.06.2012, 00:51  [ТС]     Динамическое программирование #9
Как лучше начать перебор решений?
Например, возьмем первый пример:
6 3
101101
111111
111111
3
1 4
2 6
3 1
Есть у меня массив количества единичных кирпичей в каждом ряду {6, 6, 1, 2, 1} и набор кирпичей {(1 4), (2 6), (3 1)}. Мне нужно будет отсортировать каждый массив по убыванию, а перебор начинать с максимального значения ширины кирпича и вычитать из данных кирпичей в схеме, если не получается, то начинать перебор с кирпича, следующим после максимальной ширины и так далее. Я правильно понимаю логику решения?
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
15.06.2012, 13:22  [ТС]     Динамическое программирование #10
Up!!!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.06.2012, 19:32     Динамическое программирование #11
insolent, извиняюсь, что на некоторое время оставил тему - был очень занят.
Я сейчас просто опишу алгоритм (которым сам пользовался - вполне возможно есть лучше, но вряд ли).
Допустим есть:
Цитата Сообщение от insolent Посмотреть сообщение
Есть у меня массив количества единичных кирпичей в каждом ряду {6, 6, 1, 2, 1}
Я не знаю как Вы будете хранить эти данные: может воспользуетесь массивом структур, вектором, map. Не сильно важно. Главное что бы был отсортирован по невозрастанию:
6 2// значит рядов из 6-ти кирпичей 2 штуки
2 1// значит что рядов из 2-х кирпичей одна штука
1 2// значит что рядов из 1-го кирпича 2 штуки
или так:
6 6 2 1 1
Назовем такое хранилище a[]

Затем:
Цитата Сообщение от insolent Посмотреть сообщение
и набор кирпичей {(1 4), (2 6), (3 1)}
тоже не знаю как будете хранить, но назовем такое хранилище b[]. Его тоже нужно отсортировать по неубыванию: (3 1), (2 6), (1 4).
Тогда основной код будет выглядеть так:
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
void func1(int len, int x, int t)
{
    if(len==0)
        func(t+1);
    for(i=x; i<X; i++)//перебираем имеющиеся кирипичи
    {
        if()//если размер очередного кирпича (y) меньше или равен оставшеся len
        {
            //убираем этот кирпич из b[]
            func1(len-y,i,t);
            //восстанавливаем этот кирпич обратно в b[]
        }
    }
}
 
 
void func(int t)// где t номер ряда единичных кирпичей, а сама функция перебирает все существующие ряды и вызывает другую функцию func1(), которая будет из пытаться заполнить с помощью существующего набора кирпичей 
{
    if(t==N)//если t равно количеству рядов
    {
        // выводим на экран "Yes" и заканчиваем программу
    }
    func1(b[t],0, t);// вызываем функцию, которая будет из пытаться заполнить с помощью существующего набора кирпичей t-ый ряд (в параметрах передаем размер ряда под номером t, номер кирпича с которого начинаем заполнять ряд, и номер ряда)
 
}
 
 
int main(){
    func(0);
    cout<<"No"<<endl;
 
    return 0;
}
monkaddict
Сообщений: n/a
05.09.2012, 18:22     Динамическое программирование #12
Я сейчас просто опишу алгоритм (которым сам пользовался - вполне возможно есть лучше, но вряд ли).
не затруднит ли Вас выложить реализованный Вами алгоритм на каком-либо языке. пытаюсь воплотить данный алгоритм на php. чего-то не сильно выходит.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2012, 23:10     Динамическое программирование
Еще ссылки по теме:

Динамическое программирование C++
C++ Динамическое программирование

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.09.2012, 23:10     Динамическое программирование #13
Цитата Сообщение от monkaddict Посмотреть сообщение
не затруднит ли Вас выложить реализованный Вами алгоритм на каком-либо языке.
не затруднит (код именно для указанной insolent задачи. Ввод данных из файла input.txt .Вывод результата в файл output.txt):
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
#include <stdio.h>
#define MAX 100
char a[MAX][MAX];
int b[8], fl, n, m, p;
int f(int x, int y, int k)
{
    int i;
    if(y+k>m)
        return 0;
    for(i=y; i<y+k; i++)
        if(a[x][i]=='0')
            return 0;
    return 1;
}
void rec(int x, int y)
{
    if(x==n && y==0)
    {
        fl=1;
        return;
    }
    if(!fl)
    {
        if(y<m && a[x][y]=='0')
            rec(x, y+1);
        else
        if(y==m)
            rec(x+1, 0);
        else
        {
            int i;
            for(i=7; i>=0; i--)
            {
                if(b[i] && f(x, y, i+1))
                {
                    b[i]--;
                    rec(x, y+i+1);
                    b[i]++;
                }
            }
        }       
    }
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int i, j, t;    
    scanf("%d %d\n", &m, &n);
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)      
            scanf("%c", &a[i][j]);
        scanf("\n");
    }
    scanf("%d", &p);
    for(i=0; i<p; i++)
    {
        scanf("%d", &t);
        scanf("%d", &b[t-1]);
    }   
    rec(0,0);
    if(fl)
        printf("Yes\n");
    else
        printf("No\n");
return 0;
}
Yandex
Объявления
05.09.2012, 23:10     Динамическое программирование
Ответ Создать тему
Опции темы

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