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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Структуры: база данных сотрудников фирмы http://www.cyberforum.ru/cpp-beginners/thread600927.html
Добрый вечер. Помогите пожалуйста найти ошибку в программе. Вот код: #include <stdio.h> #include <conio.h> typedef struct firm { char fam; char dolzh;
C++ Задача о рюкзаке (бесконечный выбор) Работал на C#(не очень долго) теперь вот срочно на плюсах, написал как смог! Помогите отредактировать(многих нюансов не знаю). #include "Iostream" #include "stdafx.h" namespace proect_D { class Program { http://www.cyberforum.ru/cpp-beginners/thread600925.html
C++ Метод, ошибка this
#include <iostream> #include <string> #include <fstream> class SickKoala { private: std::string name; public: std::string getName();
С++ фаил, проверка на символы C++
bool prov(char str){ int a = strlen(str); bool q = false; for (int i=0;i<a;i++) if (str!=str) q=false; else q=true; return 0; cout<< str; }
C++ Написать программу вычисления величины дохода по вкладу. http://www.cyberforum.ru/cpp-beginners/thread600914.html
Написать программу вычисления величины дохода по вкладу. Процентная ставка(% годовых) и время хранения (дней) задаются во время работы программы. Для вычисления суммы процентной ставки брать 365 дней в году. Вычисление дохода по вкладу. Величина вклада (ls):2500 Срок (дней): 30 Процентная ставка (годовых): 20 Доход: 41.10ls Сумма по окончании срока вклада: 2541.1ls ...
C++ Подключиться к процессу и производить запись в процесс Здравствуйте! Работал с процессом через ДЛЛ файл на С++, инжектил в процесс, изменял и читал память, но вот как сделать это например в C++ через *.exe? Необходимо: 1. Подключиться к процессу 2. На х32-ых системах процесс скрыт, тоесть его необходимо открыть каким-либо способом, но это сейчас не очень важно, у меня 64, но все же надо будет сделать и для 32 3. Читать память по определенному... подробнее

Показать сообщение отдельно
insolent
 Аватар для insolent
826 / 347 / 15
Регистрация: 30.01.2009
Сообщений: 1,204
08.06.2012, 20:27     Динамическое программирование
Есть такая задача:
Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 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++;
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 19:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru