← К статье

Редактируемые учебные материалы к статье. Данные кандидатов и результаты примеров вымышлены; перед использованием замените их собственными проверяемыми сведениями. Условия и ограничения указаны в статье.

Все приложения к статье
Скачать исходник

Все допустимые планы

НаборСтоимостьНагрузкаБаллы
A-B-E-G171046
B-D-G-H171046
B-C-D-G161043
B-G-H-I16943
A-B-F-G161042
A-B-C-I171041
B-D-E-G15941
B-F-H-I171041
A-B-D-G15940
B-D-E-F161039
C-D-E-I161039
A-B-D-F161038
A-C-D-I161038
A-E-F-I161038
D-F-H-I161038
A-B-G-I14837
B-D-F-G14937
B-C-D-I15936
A-B-F-I15935
D-E-F-I14933
A-D-F-I14932
B-D-G-I12732
B-D-F-I13830

Всего проверено 126 сочетаний, допустимы 23. Максимум 46 у A-B-E-G и B-D-G-H. Полные правила находятся в условии: таблица не заменяет его.

Скачать исходник

Выбор площадок: условие и решение

Все площадки, величины и баллы вымышлены. Это самостоятельная задача, не действующий тест компании.

Полное условие: выбрать четыре площадки

Команда планирует один учебный цикл измерений и должна выбрать ровно четыре из девяти площадок. У каждой заданы тип, полная стоимость посещения, нагрузка на комплект оборудования и ценность данных. Все величины условные; баллы — критерий только этой задачи.

Типы: R — городской, S — пригородный, T — удалённый. В выбранном наборе должен присутствовать хотя бы один объект каждого типа. Нельзя выбрать одну площадку дважды.

ПлощадкаТипСтоимостьНагрузкаБаллы
AR5312
BS4210
CT6415
DR327
ES5313
FT439
GT3211
HR7418
IS214

Суммарная стоимость не больше 18, нагрузка не больше 10. Равенство допускается. Посещение G требует включить B: там находится точка настройки оборудования. C и F нельзя включать вместе, потому что для них в условии требуются несовместимые комплекты.

Стоимость уже включает все затраты посещения; нагрузка складывается. Дополнительных расходов на сочетания, порядка посещения, расстояний и времени в пути нет. Поэтому задача выбирает набор, а не кратчайший маршрут. Увеличивать бюджет, арендовать второй комплект или отменять обязательный тип нельзя.

Цель — получить наибольшую сумму баллов среди допустимых наборов. Дополнительного правила выбора между равными максимумами нет. Если оптимальных наборов несколько, нужно перечислить их и не объявлять один единственно верным.

Сдать нужно выбранный набор, проверку каждого ограничения, доказательство сравнения с альтернативами и ответ при уменьшении допустимой нагрузки до девяти.

Сначала выполнимость, затем ценность

Быстро выбрать четыре самых высоких балла недостаточно. H, C, E, A дают 58, но стоят 23 и требуют нагрузку 14. Большая сумма не компенсирует два нарушения.

Есть и менее очевидные ошибки. Набор A, D, E, G укладывается в стоимость 16 и нагрузку 10, содержит все типы и даёт 43 балла. Но G требует B, которого нет. Набор A, B, C, F содержит обязательные типы, однако одновременно включает несовместимые C и F; кроме того, его нагрузка 12 превышает десять, а стоимость 19 — бюджет 18.

Первая допустимая комбинация тоже не обязательно лучшая. B, D, F, I стоит 13, требует нагрузку 8 и даёт 30. Она удовлетворяет правилам, но это лишь нижняя граница уже найденного результата. Освободившиеся деньги не являются сами по себе целью.

Удобный порядок проверки: число площадок → все три типа → зависимость G от B → несовместимость C/F → стоимость → нагрузка → сумма баллов. Последний показатель сравнивай только для прошедших наборов. Так причина отказа не теряется за привлекательной оценкой.

Полное решение и равные максимумы

Число всех наборов по четыре из девяти — 126. В этой задаче можно перебрать каждый без эвристики. После всех ограничений остаются 23 допустимых набора; максимальная сумма — 46 баллов. Её дают два варианта.

A, B, E, G: стоимость 5 + 4 + 5 + 3 = 17; нагрузка 3 + 2 + 3 + 2 = 10; баллы 12 + 10 + 13 + 11 = 46. R представлен A, S — B и E, T — G. Зависимость G выполнена через B. Несовместимой пары нет.

B, D, G, H: стоимость 4 + 3 + 3 + 7 = 17; нагрузка 2 + 2 + 2 + 4 = 10; баллы 10 + 7 + 11 + 18 = 46. R представлен D и H, S — B, T — G. B присутствует, C и F отсутствуют.

И стоимость, и нагрузка этих двух наборов совпадают. Выбрать первый по алфавиту можно как способ упорядочить вывод программы, но не как деловое преимущество: такого критерия в условии нет. Полный ответ сохраняет оба.

В списке допустимых планов приведены все 23 варианта с суммами. Это позволяет проверить не только найденные максимумы, но и утверждение «лучше нет». Переборщик работает на Python 3.9 без сторонних библиотек и выводит результаты из исходного JSON.

Доказательство полноты не сводится к слову «перебор». Если порядок не важен, число сочетаний равно 9 × 8 × 7 × 6 / (4 × 3 × 2 × 1) = 126. В генераторе каждый набор берётся один раз, проверяется по всем правилам, а максимум ищется среди прошедших. Для независимой сверки можно вместо сочетаний рассмотреть все 512 подмножеств девяти объектов и оставить только содержащие четыре. Если оба способа дают один список допустимых наборов и одинаковые максимумы, это дополнительно защищает от ошибки обхода. Всё равно сравни сами девять строк с условием: два способа могут одинаково правильно обработать неверно переписанную цифру.

Пример законченного ответа:

При исходной нагрузке десять найдено два равных лучших набора: A–B–E–G и B–D–G–H. Каждый стоит 17, использует всю допустимую нагрузку и даёт 46. Оба содержат три типа и выполняют зависимость G от B. Перебраны все 126 сочетаний, допустимы 23; ни одно не даёт больше 46. Для единственного выбора требуется дополнительный критерий, которого пока нет.

Новая вводная: комплект выдерживает девять

Оба прежних максимума требуют нагрузку 10 и становятся недопустимыми. Недостаточно зачеркнуть одну единицу в итоговой строке: нужно заново выбрать ровно четыре площадки и пересчитать остальные правила.

При нагрузке не больше девяти остаются 11 допустимых наборов. Максимум — 43 балла, и он единственный: B, G, H, I.

Проверка: стоимость 4 + 3 + 7 + 2 = 16; нагрузка 2 + 2 + 4 + 1 = 9; баллы 10 + 11 + 18 + 4 = 43. H даёт тип R, B и I — S, G — T. Зависимость G выполнена, несовместимой пары нет.

Ответ на изменение:

Отзываю прежние два варианта: они не проходят новую нагрузку. При девяти выбираю B–G–H–I: стоимость 16, нагрузка 9, баллы 43. Проверка всех сочетаний оставляет 11 допустимых наборов, среди них это единственный максимум. Уменьшение результата с 46 до 43 связано с новым ограничением, а не с ошибкой первоначального расчёта.

Здесь видно качество пересмотра: правило изменилось явно, прежний результат сохранён как версия, новый вывод доказан по тем же данным. Не нужно защищать старый набор после изменения условия.

Скачать исходник

Код проверки: solve.py

"""Original four-site set selection; Python 3.9 standard library."""
import itertools,json
from pathlib import Path
def validate(d):
 for key in ("choose","budget","capacity"):
  if not isinstance(d[key],int) or isinstance(d[key],bool) or d[key]<0:raise ValueError("Invalid bound")
 ids=[s["id"] for s in d["sites"]]
 if len(ids)!=len(set(ids)):raise ValueError("Duplicate sites")
 for s in d["sites"]:
  for key in ("cost","load","score"):
   if not isinstance(s[key],int) or isinstance(s[key],bool) or s[key]<0:raise ValueError("Invalid site number")
 if d["choose"]<1 or d["choose"]>len(ids):raise ValueError("Invalid selection size")
 for a,b in list(d["requires"].items())+d["incompatible"]:
  if a not in ids or b not in ids:raise ValueError("Unknown dependency site")
def assess(d,ids):
 by={s["id"]:s for s in d["sites"]}
 if len(ids)!=len(set(ids)) or any(i not in by for i in ids):raise ValueError("Invalid selected identifiers")
 rows=[by[i] for i in ids];reasons=[]
 if len(rows)!=d["choose"]:reasons.append("count")
 if not set(d["required_types"])<={s["type"] for s in rows}:reasons.append("types")
 if any(a in ids and b not in ids for a,b in d["requires"].items()):reasons.append("dependency")
 if any(set(pair)<=set(ids) for pair in d["incompatible"]):reasons.append("incompatible")
 cost=sum(s["cost"] for s in rows);load=sum(s["load"] for s in rows);score=sum(s["score"] for s in rows)
 if cost>d["budget"]:reasons.append("budget")
 if load>d["capacity"]:reasons.append("capacity")
 return {"ids":sorted(ids),"cost":cost,"load":load,"score":score,"reasons":reasons}
def solve(d):
 validate(d);all_rows=[assess(d,ids) for ids in itertools.combinations([s["id"] for s in d["sites"]],d["choose"])]
 feasible=[r for r in all_rows if not r["reasons"]];best=max((r["score"] for r in feasible),default=None)
 return {"examined":len(all_rows),"feasible_count":len(feasible),"best_score":best,"best":[r for r in feasible if r["score"]==best],"feasible":feasible}
if __name__=="__main__":
 print(json.dumps(solve(json.loads(Path(__file__).with_name("sites.json").read_text())),indent=2))
Скачать исходник

Код проверки: verify.py

"""Independent bitmask enumeration and fixed selection answers."""
import copy,json,sys
from pathlib import Path
from solve import solve,assess
def check(condition,message):
 if not condition:raise AssertionError(message)
def independent(d):
 # Enumerate all 512 subsets; constraints evaluated directly.
 rows=d["sites"];valid=[]
 for mask in range(1<<len(rows)):
  chosen=[rows[i] for i in range(len(rows)) if mask&(1<<i)]
  if len(chosen)!=4:continue
  ids={s["id"] for s in chosen}
  if {s["type"] for s in chosen}!={"R","S","T"}:continue
  if "G"in ids and "B"not in ids:continue
  if "C"in ids and "F"in ids:continue
  if sum(s["cost"] for s in chosen)>d["budget"] or sum(s["load"] for s in chosen)>d["capacity"]:continue
  valid.append(("".join(sorted(ids)),sum(s["score"] for s in chosen)))
 return sorted(valid)
def main():
 d=json.loads(Path(__file__).with_name("sites.json").read_text());r=solve(d)
 check((r["examined"],r["feasible_count"],r["best_score"])==(126,23,46),"Fixed base counts/score")
 check({"".join(x["ids"]) for x in r["best"]}=={"ABEG","BDGH"},"All equal maxima")
 check(sorted(("".join(x["ids"]),x["score"]) for x in r["feasible"])==independent(d),"Independent subset enumeration")
 for ids,reason in (("ADEG","dependency"),("ABCF","incompatible"),("ACEH","budget"),("BDFI",None)):
  reasons=assess(d,list(ids))["reasons"]
  check((reason in reasons) if reason else not reasons,"Constraint case "+ids)
 changed=copy.deepcopy(d);changed["capacity"]=9;r=solve(changed)
 check((r["feasible_count"],r["best_score"])==(11,43) and ["".join(x["ids"]) for x in r["best"]]==["BGHI"],"Capacity9")
 check(sorted(("".join(x["ids"]),x["score"]) for x in r["feasible"])==independent(changed),"Independent capacity9")
 changed=copy.deepcopy(d);changed["budget"]=0;r=solve(changed)
 check(r["feasible_count"]==0 and r["best_score"]is None and r["best"]==[],"No feasible plan")
 bads=[]
 bad=copy.deepcopy(d);bad["sites"][0]["load"]=-1;bads.append(bad)
 bad=copy.deepcopy(d);bad["sites"][0]["id"]="B";bads.append(bad)
 bad=copy.deepcopy(d);bad["requires"]["G"]="Z";bads.append(bad)
 for bad in bads:
  try:solve(bad)
  except ValueError:pass
  else:raise AssertionError("Invalid input accepted")
 try:assess(d,["A","A","B","G"])
 except ValueError:pass
 else:raise AssertionError("Duplicate selection accepted")
 print(json.dumps({"examined":126,"feasible":23,"equal_optima":2,"independent_masks":512,"capacity9_optimum":"BGHI","no_feasible_plan":True,"invalid_inputs_rejected":4}))
if __name__=="__main__":
 try:main()
 except Exception as error:print("FAIL: "+str(error),file=sys.stderr);sys.exit(1)