Весы

@piligrimm0 · Регистрация: 24.08.2020

Есть Вот такая задача. Условие во вложении. Не понимаю, как к ней подступиться со стороны жадного алгоритма (указано, что решается через него). Хотелось бы получить разъяснения и ваши предложения с идеями в реализации. Заранее спасибо!

@_Ivana · 07.10.2020, 01:11

Сообщение от piligrimm0

со стороны жадного алгоритма (указано, что решается через него)

очевидно, что нет

C++

int m[100], d[5001][100];
 
bool f (int s, int i) {
    if (s == 0) return true;
    else if (s < 0 || i < 0) return false;
    else if (d[s][i] == 0) d[s][i] = (f(s-m[i], i-1) || f(s, i-1)) + 1;
    return d[s][i] - 1;
}
 
int main() {
    int n, s=0; std::cin >> n; for (int i=0; i<n; i++) { std::cin >> m[i]; s += m[i]; }
    std::cout << (s%2 ? "NO" : f(s/2, n-1) ? "YES" : "NO");
}

Код

Тест	Статус	Время работы	Астрономическое время работы	Используемая память
1	OK		0.002	0.003	3915776
2	OK		0.001	0.002	3923968
3	OK		0.001	0.002	3923968
4	OK		0.001	0.002	3923968
5	OK		0.001	0.002	3923968
6	OK		0.001	0.002	3923968
7	OK		0.001	0.002	3923968
8	OK		0.001	0.002	3923968
9	OK		0.001	0.003	3923968
10	OK		0.001	0.003	3923968
11	OK		0.001	0.003	3923968
12	OK		0.002	0.003	3923968
13	OK		0.001	0.003	3915776
14	OK		0.001	0.002	3923968
15	OK		0.002	0.003	3923968
16	OK		0.001	0.002	3923968
17	OK		0.001	0.002	4059136
18	OK		0.001	0.002	3923968
19	OK		0.002	0.003	3915776
20	OK		0.001	0.003	3923968
21	OK		0.001	0.002	3923968
22	OK		0.001	0.002	3923968
23	OK		0.001	0.003	3915776
24	OK		0.001	0.002	4059136
25	OK		0.001	0.002	3923968
26	OK		0.001	0.002	3923968
27	OK		0.001	0.002	3923968
28	OK		0.002	0.003	3923968
29	OK		0.001	0.003	3923968
30	OK		0.001	0.002	3923968
31	OK		0.001	0.003	4059136
32	OK		0.001	0.003	3923968
33	OK		0.001	0.003	3923968
34	OK		0.001	0.002	4059136
35	OK		0.001	0.002	3915776
36	OK		0.001	0.003	3923968
37	OK		0.001	0.003	3923968
38	OK		0.001	0.003	3923968
39	OK		0.001	0.003	3923968
40	OK		0.001	0.002	3923968
41	OK		0.001	0.003	3923968
42	OK		0.001	0.003	3923968
43	OK		0.002	0.003	3923968
44	OK		0.002	0.003	3923968
45	OK		0.001	0.002	3923968
46	OK		0.001	0.003	4059136
47	OK		0.001	0.003	3923968
48	OK		0.001	0.002	3923968
49	OK		0.002	0.004	4059136
50	OK		0.001	0.003	3923968

@мама Стифлера · 07.10.2020, 01:41

_Ivana, отлично работает. Можно узнать, что за алгоритм вычисления такой?

@_Ivana · 07.10.2020, 01:48

ДП через рекурсию, как и всегда

@piligrimm0 · 07.10.2020, 02:06 **[ТС]**

Огромное спасибо

@piligrimm0 0 / 0 / 0 Регистрация: 24.08.2020 Сообщений: 7
		1
	Весы 07.10.2020, 00:25. Показов 1561. Ответов 4 Метки нет (Все метки) Есть Вот такая задача. Условие во вложении. Не понимаю, как к ней подступиться со стороны жадного алгоритма (указано, что решается через него). Хотелось бы получить разъяснения и ваши предложения с идеями в реализации. Заранее спасибо! Миниатюры __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

@мама Стифлера из племени тумба-юбма 2348 / 1691 / 390 Регистрация: 29.11.2015 Сообщений: 8,199 Записей в блоге: 14
	07.10.2020, 01:41	3
	_Ivana, отлично работает. Можно узнать, что за алгоритм вычисления такой? 0

@_Ivana 4814 / 2275 / 287 Регистрация: 01.03.2013 Сообщений: 5,936 Записей в блоге: 26
	07.10.2020, 01:48	4
	ДП через рекурсию, как и всегда 0

@piligrimm0 0 / 0 / 0 Регистрация: 24.08.2020 Сообщений: 7
	07.10.2020, 02:06 [ТС]	5
	Огромное спасибо 0

Опции темы

Весы

Решение