Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Таблица 9.1.
Пример задачи о рюкзаке для трех предметов
Предмет
Вместимость рюкзака
0 фунтов
1 фунт
2 фунта
3 фунта
Спички (1 фунт, 5 долларов)
0
5
5
5
Фонарик (2 фунта, 10 долларов)
0
5
10
15
Книга (1 фунт, 15 долларов)
0
15
20
25
Если.просматривать.таблицу.слева.направо,.то.вес.предметов,.которые.вы.пы-
таетесь.уместить.в.рюкзаке,.увеличивается..Если.просматривать.таблицу.сверху.
вниз,.то.увеличивается.количество.предметов,.которые.вы.пытаетесь.поместить.
в.рюкзак..В.первом.ряду.вы.пробуете.поместить.в.рюкзак.только.спички..Во.
втором.ряду.выбираете.наиболее.ценную.комбинацию.из.спичек.и.фонарика,.
которая.может.поместиться.в.рюкзак..В.третьем.ряду.находите.самую.ценную.
комбинацию.из.всех.трех.предметов.
В.качестве.упражнения,.которое.поможет.вам.лучше.понять.задачу,.попробуйте.
заполнить.пустую.версию.этой.таблицы.самостоятельно,.используя.алгоритм,.
описанный.в.функции.
knapsack()
,.и.эти.же.три.предмета..Затем.примените.алго-
ритм,.представленный.в.конце.функции,.чтобы.выбрать.из.таблицы.правильные.
предметы..Эта.таблица.соответствует.переменной.
table
.в.функции.
9.2. ЗАДАЧА КОММИВОЯЖЕРА
Проблема.коммивояжера.—.классическая.и.одна.из.наиболее.широко.обсуждаемых.
задач.во.всей.теории.вычислений..Коммивояжер.должен.посетить.все.города.на.
карте.ровно.один.раз.и.вернуться.в.конце.путешествия.в.город,.с.которого.начался.
маршрут..Между.любыми.двумя.городами.существует.прямая.дорога,.и.коммиво-
яжер.может.посещать.города.в.любом.порядке..Каков.самый.короткий.маршрут?
Эту.задачу.можно.представить.как.графовую.(см..главу.4),.в.которой.города.—.
это.вершины,.а.дороги.между.ними.—.ребра..Вашим.первым.побуждением.может.
быть.желание.найти.минимальное.связующее.дерево,.как.описано.в.главе.4..К.со-
жалению,.решить.задачу.коммивояжера.не.так.просто..Минимальное.связующее.
дерево.—.это.кратчайший.путь.для.соединения.всех.городов,.но.оно.не.обеспечи-
вает.кратчайшего.пути.для.посещения.всех.городов.ровно.один.раз.

---