В процессе взаимной критики выяснилось, что обе llm хреново распознали таблицу. Ручками внёс несколько изменений, даже не вникал в суть задачи. Попросил найти оптимальное решение и строго доказать, что лучше решения не найти.
В результате споров оптимальное решение нашёл Deepseek. Qwen согласился с доводами и в дальнейшем выступал в роли рецензента.
В чем Deepseek неправ? Является ли решение оптимальным. Найдите решение лучше, если это не так.
Решение под спойлером
Финальный ответ (с исправлением всех цен)
---
Условие задачи
Денис нанимает армию из существ со следующими параметрами (город не указан, просто «город»):
Существо Золото Драгоценные камни Ртуть Сила Доступно
Титан 5000 3 1 300 10
Нага 1500 2 0 120 20
Джинн 750 1 1 60 30
Маг 500 1 1 40 55
Голем 400 0 1 35 60
Горгулья 200 0 0 20 110
Гремлин 70 0 0 4 500
Ресурсы: 200000 золота, 115 драгоценных камней, 80 ртути.
Камни можно продавать по 500 зол./шт.
Цель: максимизировать суммарную силу.
Дополнительные условия:
· Сила дальнего боя (Титаны + Маги + Гремлины) ≥ 4000.
· Сила летающих (Джинны + Горгульи) ≥ 2000.
---
Математическая модель
Переменные:
x_1…x_7 – количество каждого существа (в порядке таблицы),
s – проданные камни (0 \le s \le 115, целое).
Целевая функция:
\max Z = 300x_1 + 120x_2 + 60x_3 + 40x_4 + 35x_5 + 20x_6 + 4x_7
Ограничения:
1. Золото:
5000x_1 + 1500x_2 + 750x_3 + 500x_4 + 400x_5 + 200x_6 + 70x_7 \le 200000 + 500s
2. Камни (после продажи):
3x_1 + 2x_2 + x_3 + x_4 \le 115 - s
3. Ртуть:
x_1 + x_3 + x_4 + x_5 \le 80
4. Лимиты:
0 \le x_1 \le 10,\; 0 \le x_2 \le 20,\; 0 \le x_3 \le 30,\; 0 \le x_4 \le 55,\; 0 \le x_5 \le 60,\; 0 \le x_6 \le 110,\; 0 \le x_7 \le 500
(все целые).
5. Дальний бой:
300x_1 + 40x_4 + 4x_7 \ge 4000
6. Летающие:
60x_3 + 20x_6 \ge 2000
---
Оптимальное решение (единственное)
\boxed{x_1=10,\; x_2=20,\; x_3=30,\; x_4=15,\; x_5=25,\; x_6=110,\; x_7=500,\; s=0}
Проверка ресурсов (правильные цены):
Существо Кол-во Цена Сумма золота
Титан 10 5000 50000
Нага 20 1500 30000
Джинн 30 750 22500
Маг 15 500 7500
Голем 25 400 10000
Горгулья 110 200 22000
Гремлин 500 70 35000
Итого 177000
· Золото: остаток 200\,000 - 177\,000 = 23\,000 (золото не является связывающим).
· Камни: 3·10 + 2·20 + 1·30 + 1·15 = 30+40+30+15 = 115 – все использованы.
· Ртуть: 1·10 + 0·20 + 1·30 + 1·15 + 1·25 = 10+0+30+15+25 = 80 – вся использована.
Общая сила:
300·10 + 120·20 + 60·30 + 40·15 + 35·25 + 20·110 + 4·500 = 3000+2400+1800+600+875+2200+2000 = \mathbf{12\,875}.
Проверка дополнительных условий:
· Дальний бой: 300·10 + 40·15 + 4·500 = 3000+600+2000 = 5600 \ge 4000.
· Летающие: 60·30 + 20·110 = 1800+2200 = 4000 \ge 2000.
---
Строгое доказательство оптимальности
1. Существа без затрат камней и ртути (Горгульи, Гремлины) всегда выгодно брать по максимуму, так как они дают положительную силу, не влияют на дефицитные ресурсы, и золота хватает (в оптимальном решении затраты 177000 < 200000). Поэтому x_6=110,\; x_7=500. Их вклад в силу = 2200 + 2000 = 4200.
2. Оставшаяся задача – выбор x_1..x_5 при ограничениях на камни и ртуть.
Эффективность по камням:
· Титан: 300/3 = 100 (наивысшая),
· Нага: 120/2 = 60,
· Джинн: 60/1 = 60,
· Маг: 40/1 = 40.
Так как камни – лимитирующий ресурс (их 115 и они полностью расходуются в оптимуме), все они должны быть отданы существам с наибольшей эффективностью, пока не исчерпаются их лимиты. Поэтому берём всех Титанов (10), всех Наг (20), всех Джиннов (30). Это требует 100 камней и 40 ртути, даёт силу 3000+2400+1800 = 7200.
3. Остаётся 15 камней и 40 ртути. Эти камни могут пойти только на Магов (так как остальные «каменные» существа уже набраны по максимуму). Каждый Маг даёт 40 силы за 1 камень + 1 ртуть. Все 15 камней выгоднее отдать Магам, чем продать (продажа даст золото, но золото не ограничивает, а дополнительная сила от найма Големов за счёт ртути меньше – 35 против 40). Поэтому x_4=15, расходует 15 ртути. Остаётся 80-40-15=25 ртути, которые идут на Големов – x_5=25. Сила этой части: 15·40 + 25·35 = 600+875 = 1475.
4. Проверка альтернатив:
· Уменьшить Титана – освободится 3 камня и 1 ртуть. Максимальная сила из этих ресурсов (например, 1 Нага + 1 Джинн = 180, или 3 Мага = 120) меньше 300, поэтому невыгодно.
· Уменьшить Нагу – 2 камня дают 120 силы, альтернатива (2 Мага = 80, или 1 Джинн + 1 Маг = 100) хуже.
· Уменьшить Джинна – 1 камень + 1 ртуть дают 60 силы, замена на Мага (40) или Голема (35) хуже; замена на Мага+Голема дала бы 75, но требует 2 ртути вместо 1, а вся ртуть уже использована – такая замена невозможна.
· Заменить Мага на Голема – потеря 5 силы за каждую замену.
Следовательно, никакое другое целочисленное распределение не даёт большей силы.
5. Дополнительные ограничения выполняются с запасом, поэтому они не меняют выбор.
6. Итог:
Z_{\max} = 4200 + 7200 + 1475 = 12875.
Ответ: максимальная сила армии равна 12 875, достигается единственным набором (10,20,30,15,25,110,500) без продажи камней. Остаток золота – 23 000.