Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
yarik2550
1 / 1 / 0
Регистрация: 10.02.2016
Сообщений: 43
#1

Решить задачу методом рекурсивного перебора с возвратом

22.05.2016, 01:52. Просмотров 1280. Ответов 26
Метки нет (Все метки)

В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
Пример
ВХОДНЫЕ ДАННЫЕ
C++
1
2
100 6
11 20 30 40 11 99
ВЫХОДНЫЕ ДАННЫЕ
C++
1
2
3
40 30 30
Мой код слишком долго работает при M=15
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
#include <iostream>
#include <vector>
#include <string>
#include<set>
#include<math.h>
#include <algorithm>
using namespace std;
int main()
{
 
    long long n, m, a, kirp = 0, razm = 0;
    long long min1 = 9999999999; string str, str1;
    int minit = -92187452;
    cin >> n >> m;
    vector<int>v; vector<int>c(m);
    long long ch;
    long long k = 0;
    while (k != m&&cin >> a)
    {
        k++;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    reverse(v.begin(),v.end());
    int tr = 0;
    for (int i = 0; i < m; i++)
    {
        c[i] = 0;
        if (v[i] == v[0])
        {
            tr++;
        }
    }
    if (tr == v.size() && v[0]>n)
    {
        cout << 0; return 0;
    }
    for (int d = 1; d <pow(3, m); d++)
    {
        int s;
        long long l = m - 1;
        while (c[l] == 2)
        {
            c[l] = 0;
            l--;
            if (l < 0)
            {
                break;
            }
        }
        if (l >= 0)
        {
            c[l]++;
        }
        long long ch = 0;
        int frf = 0;
        str.clear();
        for (int j = 0; j < m; j++)
        {
            ch += c[j] * v[j];
            if (ch > n)
            {
                razm = 1; s = n + 1; break;
            }
            s += ch;
            if (s > n)
            {
                break;
            }
            str += (c[j] + 48);
        }
        long long ch1 = 0;
        if (frf == 1)
        {
            continue;
        }
        if (ch == n)
        {
            ch1 = 0;
            for (int i = 0; i < str.size(); i++)
            {
                ch1 += str[i] - 48;
            }
            if (ch1 < min1)
            {
                min1 = ch1;
                minit = d;
                str1 = str;
            }
        }
 
    }
    if (minit == -92187452 && razm == 1)
    {
        cout << 0; system("pause"); return 0;
    }
    else
    {
        if (minit == -92187452 && razm == 0)
        {
            cout << -1; system("pause"); return 0;
        }
    }
    string otvet = str1;
    cout << min1 << endl;
    for (int i = 0; i < otvet.length(); i++)
    {
        long long t = otvet[i] - 48;
        while (t != 0)
        {
            cout << v[i] << " ";
            t--;
        }
    }
}
Помогите решить эту задачу методом рекурсивного перебора с возвратом,пожалуйста
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2016, 01:52
Ответы с готовыми решениями:

Решить транспортную задачу методом потенциалов
Помогите пожалуйста. Необходимо написать программу которая решает транспортную...

Поиск наибольшей общей подпоследовательности методом методом полного перебора
Здравствуйте! Помогите пожалуйста с этим адом :wall: Нужно решить задачу о...

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска...

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска...

Поиск массива методом последовательного перебора
Поиск массива методом последовательного перебора в С++

26
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
23.05.2016, 15:17 #21
Странно. Вчера вечером я как раз реализовал такую схему отсечений, даже дополнительный накопительный суффиксальный массив сумм списка монет предварительно рассчитал для этого. Это уменьшило время на остальных тестах, но не затронуло 25-й. Может посмотрю еще вечером...
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.05.2016, 16:13 #22
Цитата Сообщение от _Ivana Посмотреть сообщение
массив сумм списка монет
Вообще-то они в условии грозятся, что одна монетка может весить до миллиарда, в таком случае сумма не поместится в int. Кстати, я из-за этого отбросил вариант с суммами, а зря, оказывается, так как он-то и оказался самым быстрым! Тринадцать тестов проходит за нулевое время, в том числе и 25-й:
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
///////////////////////////////////////////////////////////////////////////////
//Вариант 9.
///////////////////////////////////////////////////////////////////////////////
//http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=32&run_id=36r8533#1
//Задача №32. Монетки
 
//Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран
//или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.
 
//Ограничение по времени, сек   2
//Ограничение по памяти, мегабайт   64
 
//В Волшебной стране используются монетки достоинством A1, A2,…, AM.
//Волшебный человечек пришел в магазин и обнаружил, что у него есть
//ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N.
//Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
 
//Входные данные
 
//Сначала вводится число N (1≤N≤10^9), затем — число M (1≤M≤15) и далее M
//попарно различных чисел A1, A2,…, AM (1≤Ai≤10^9).
//Выходные данные
 
//Выведите сначала K — количество монет, которое придется отдать
//Волшебному человечку, если он сможет заплатить указанную сумму без сдачи.
//Далее выведите K чисел, задающих достоинства монет. Если решений несколько,
//выведите вариант, в котором Волшебный человек отдаст наименьшее возможное
//количество монет. Если таких вариантов несколько, выведите любой из них.
 
//Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного
//человечка не хватит денег, чтобы заплатить указанную сумму, выведите
//одно число –1 (минус один).
 
//Оценка задачи
 
//1 балл получат программы, правильно решающие задачу с дополнительными
//ограничениями Ai≤106, M≤10.
 
//Примеры
//Входные данные
 
//5 2
//1 2
 
//Выходные данные
 
//3
//2 2 1
 
//Входные данные
 
//7 2
//1 2
 
//Выходные данные
 
//-1
 
//Входные данные
 
//5 2
//3 4
 
//Выходные данные
 
//0
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >   T_int_values;
///////////////////////////////////////////////////////////////////////////////
void    pay
    (
        int                         amount,
        int                         active_money,
        T_int_values    const   &   coins_values,
        int                         count_of_each_val,
 
        int                     &   res_total_counter,
        T_int_values            &   res_counters,
        bool                    &   bool_res,
 
        int                         total_counter   =   0,
        T_int_values                counters        =   {}
    )
{
    if  (
            !amount
        )
    {
 
        bool    total_counter_is_valid    =     !res_total_counter
 
                                            ||      total_counter
                                                <   res_total_counter;
 
        if  (
                    !bool_res
                ||  total_counter_is_valid
            )
        {
            res_total_counter   =   total_counter;
            res_counters        =   counters;
            bool_res            =   true;
        }//if
    }
    else if (
                    active_money
                >=  amount
            )
    {
        size_t  ind                 =       coins_values    .size()
                                        -   1
                                        -   counters        .size();
 
        auto    coin_val_cur        =   coins_values[ ind ];
 
        auto    active_money_new    =       active_money
 
                                        -       coin_val_cur
                                            *   count_of_each_val;
 
        int     counter_max         =   std::min
                                            (
                                                count_of_each_val,
                                                amount / coin_val_cur
                                            );
 
        for( int  counter{ counter_max }; counter >= 0; --counter )
        {
            auto    amount_new          =       amount
 
                                            -       coin_val_cur
                                                *   counter;
 
            auto    total_counter_new   =       total_counter
                                            +   counter;
 
            auto    counters_new        =   counters;
            counters_new.push_back( counter );
 
            pay (
                    amount_new,
                    active_money_new,
                    coins_values,
                    count_of_each_val,
 
                    res_total_counter,
                    res_counters,
                    bool_res,
 
                    total_counter_new,
                    counters_new
                );
        }//for
    }//else if
}
///////////////////////////////////////////////////////////////////////////////
void    try_to_pay_and_print_result
    (
        int             amount,
        T_int_values    coins_values,
        int             count_of_each_val
    )
{
    std::sort
        (
            coins_values.begin  (),
            coins_values.end    ()
        );
 
    int             res_total_counter{};
    T_int_values    res_counters;
 
    int             active_money   =        std::accumulate
                                                (
                                                     coins_values.begin      (),
                                                     coins_values.end        (),
                                                     0
                                                )
 
                                        *   count_of_each_val;
 
    if  (
                amount
            >   active_money
        )
    {
        std::cout   <<  -1;
    }
    else
    {
        bool    bool_res{};
 
        pay (
                amount,
                active_money,
                coins_values,
                count_of_each_val,
 
                res_total_counter,
                res_counters,
                bool_res
            );
 
        if( bool_res )
        {
            std::cout   <<  res_total_counter
                        <<  std::endl;
 
            for( size_t  i{}; i < res_counters.size(); ++i )
            {
                for( int  count{}; count < res_counters[i]; ++count )
                {
                    std::cout   <<  coins_values
                                        [
                                                coins_values.size()
                                            -   1
                                            -   i
                                        ]
 
                                <<  ' ';
                }//for
            }//for
        }
        else
        {
            std::cout   <<  0;
        }//else
    }//else
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    const   int     COUNT_OF_EACH_VAL   =   2;
    int             amount              {};
    int             coin_values_total   {};
 
    std::cin    >>  amount;
    std::cin    >>  coin_values_total;
 
    T_int_values  coins_values( coin_values_total );
 
    for (
            auto    &   coin_val    :
            coins_values
        )
    {
        std::cin    >>  coin_val;
    }
 
    try_to_pay_and_print_result
        (
            amount,
            coins_values,
            COUNT_OF_EACH_VAL
        );
}
0
Миниатюры
Решить задачу методом рекурсивного перебора с возвратом  
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
23.05.2016, 23:21 #23
Цитата Сообщение от Mr.X Посмотреть сообщение
в таком случае сумма не поместится в int
не страшно - у нас лонг лонги есть. А у обладателей нормальных компиляторов (по слухам) - целые любой байтовой разрядности, как и должно было быть с самого начала появления языка С и как есть у любого ассемблерщика, но не будем о грустном.

Цитата Сообщение от Mr.X Посмотреть сообщение
Кстати, я из-за этого отбросил вариант с суммами, а зря, оказывается, так как он-то и оказался самым быстрым!
Именно, всегда быстрее рассчитать заранее все что можно рассчитать, а потом использовать это. Хотя и непонятно, почему у меня не срабатывает на 25 тесте, но сама идея не нова.

Добавлено через 7 часов 0 минут
Вести с полей. Не знаю, что вчера я не учел (может поздно ночью хуже соображал), но сегодня мои отсечения без сортировки проходят все тесты за такие времена:
1 OK 0.001 0.002 1441792
2 OK 0.001 0.003 1441792
3 OK 0.001 0.002 1441792
4 OK 0.001 0.004 1441792
5 OK 0.001 0.002 1441792
6 OK 0.001 0.002 1441792
7 OK 0.001 0.003 1441792
8 OK 0.001 0.002 1441792
9 OK 0.001 0.002 1441792
10 OK 0.001 0.003 1441792
11 OK 0.001 0.002 1441792
12 OK 0.001 0.002 1441792
13 OK 0.001 0.003 1441792
14 OK 0.001 0.004 1441792
15 OK 0.002 0.004 1441792
16 OK 0.001 0.004 1441792
17 OK 0.001 0.002 1441792
18 OK 0.001 0.003 1441792
19 OK 0.001 0.003 1441792
20 OK 0.001 0.002 1441792
21 OK 0.001 0.002 1441792
22 OK 0.001 0.003 1441792
23 OK 0.001 0.003 1441792
24 OK 0.002 0.004 1441792
25 OK 0.871 1.015 1585152
а с предварительной сортировкой массива по убыванию - за такие:
1 OK 0.001 0.003 1441792
2 OK 0.001 0.003 1441792
3 OK 0.001 0.002 1441792
4 OK 0.001 0.003 1441792
5 OK 0.001 0.003 1441792
6 OK 0.001 0.002 1441792
7 OK 0.001 0.003 1441792
8 OK 0.001 0.003 1441792
9 OK 0.001 0.004 1441792
10 OK 0.001 0.002 1441792
11 OK 0 0.002 1441792
12 OK 0.001 0.003 1441792
13 OK 0 0.002 1441792
14 OK 0.001 0.004 1441792
15 OK 0 0.002 1441792
16 OK 0.001 0.002 1441792
17 OK 0 0.002 1441792
18 OK 0.001 0.003 1441792
19 OK 0 0.002 1441792
20 OK 0.001 0.003 1441792
21 OK 0 0.002 1441792
22 OK 0.001 0.003 1441792
23 OK 0 0.002 1441792
24 OK 0.001 0.002 1441792
25 OK 0.001 0.002 1441792
Так что все в порядке, мин нет
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
24.05.2016, 03:21 #24
Цитата Сообщение от _Ivana Посмотреть сообщение
а с предварительной сортировкой массива по убыванию - за такие:
Ну вот видите, а кто-то скептически отзывался о сортировке!
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
24.05.2016, 03:30 #25
Вижу. Но позволю себе пояснить мой скептицизм. На другом примере отсечений, которые я применил в самом первом варианте решения этой задачи - а именно: если при текущем поиске мы уже набрали монет больше, чем при текущем промежуточном оптимальном решении - нам надо прекращать поиск. Верная оптимизация? Да, верная. Будет хорошо работать? Да, будет. В БОЛЬШИНСТВЕ СЛУЧАЕВ. То есть, мы оптимизируем средний набор входных данных. Но всегда можно подобрать такой набор, при котором наши решения будут получаться с каждым разом все лучше и лучше, и на этих данных эта оптимизация не сработает. Так нужна ли она? В боевом коде - я считаю, да. Но в общем случае асимптотика алгоритма не изменится, ибо считается по худшему случаю. В последующих кодах я эту оптимизацию НЕ ПРИМЕНЯЛ.

Так и с сортировкой здесь, имхо. Есть алгоритмы, в которых очевидно и доказывается, что сортировка улучшает асимптотику в любом случае. даже наихудшем. В данном алгоритме я этого не вижу, хотя и утверждать отсутствие этого не берусь. А что в 25 тесте звезды и данные так сошлись, что сортировка помогла - ну.... я бы сказал, что это в каком-то смысле нечестные тесты.

ЗЫ а вообще я просто поленился сначала нагуглить как делать сортировку массива по убыванию с использованием своей функции-компаратора Ну и надеялся на то, что не будет подтасовочных тестов под определенные условия и методы...
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
24.05.2016, 03:37 #26
Цитата Сообщение от _Ivana Посмотреть сообщение
Вижу. Но позволю себе пояснить мой скептицизм.
Что-то вы как-то сложно рассуждаете! Если монет нужно как можно меньше, то очевидно, что надо стараться брать как можно более крупные.
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
24.05.2016, 03:43 #27
90 + 10 единиц или 50 + 50... А еще на может быть надо набрать маленькую сумму... Хотя тут крупные отсекаются сразу, вы правы. Но если взять пример всех монет разного близкого и четного номинала, и набирать сумму на 1 меньше их удвоенной суммы - то тут хоть обсортируйся - придется все перебрать. Хотя здесь отлично помогает отсечение по оставшейся накопительной сумме... В общем, мне пока не все так очевидно.
0
24.05.2016, 03:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2016, 03:43

Решение нелинейного уравнения методом перебора
Решить уравнение sin(1/x)=0 методом перебора на промежутке x = .

Функция с возвратом указателя и возвратом ссылки
Найти максимальный и минимальный элемент в двумерном массиве и указать их...

Решение уравнения методом перебора (сокращение кода)
A*X3 + B*X2 + C*X + D = 0 нужно решить это уравнение методом перебора корни...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru