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

double 
prevItemValue = table[i][capacity];
if 
(capacity >= item.weight) { // предмет помещается в рюкзак
prevItemValue
.—.это.значение.последней.комбинации.предметов.для.текущей.ис-
следуемой.вместимости.рюкзака..Для.каждой.возможной.комбинации.предметов.
мы.проверяем,.можно.ли.добавить.в.рюкзак.еще.один.новый.элемент.

---

248
Глава 9.
Другие задачи
Если.предмет.весит.больше,.чем.позволяет.рассматриваемая.вместимость.рюкзака,.
то.мы.просто.копируем.значение.для.последней.комбинации.предметов,.которую.
рассматривали.для.данной.вместимости:
else 
{ // для этого предмета нет места
table[i + 1][capacity] = prevItemValue;
}
В.противном.случае.проверяем,.приведет.ли.добавление.нового.предмета.к.более.
высокой.стоимости.всего.украденного,.чем.последнее.сочетание.предметов.для.
той.вместимости.рюкзака,.которую.мы.рассматриваем..Для.этого.мы.прибавляем.
стоимость.предмета.к.значению,.уже.вычисленному.в.таблице.для.предыдущей.
комбинации.предметов..Если.это.значение.больше,.чем.значение.для.последней.
комбинации.предметов.для.текущей.вместимости,.то.вставляем.его.в.таблицу,.
если.же.нет.—.вставляем.последнее.значение:
double 
valueFreeingWeightForItem = table[i][capacity — item.weight];
// только если этот предмет более ценный, чем предыдущий
table[i + 1][capacity] = Math.
max
(valueFreeingWeightForItem + item.value,
prevItemValue);
На.этом.составление.таблицы.завершается..Однако.для.того,.чтобы.действитель-
но.узнать,.какие.предметы.будут.в.решении,.нужно.проделать.обратную.работу.
для.максимальной.вместимости.и.результирующей.исследуемой.комбинации.
предметов:
for 
(
int 
i = items.size(); i > 0; i--) { // идем в обратном направлении
// был ли предмет использован?
if 
(table[i — 1][capacity] != table[i][capacity]) {
Мы.начинаем.с.конца.и.перебираем.таблицу.справа.налево,.на.каждом.этапе.про-
веряя,.было.ли.изменено.значение,.вставленное.в.нее..Если.изменено,.значит,.мы.
добавили.новый.предмет,.который.рассматривался.в.данной.комбинации,.потому.
что.эта.комбинация.оказалась.более.ценной,.чем.предыдущая..Поэтому.мы.до-
бавляем.этот.предмет.в.решение..Кроме.того,.по.мере.перемещения.по.таблице.
вместимость.рюкзака.уменьшается.на.вес.предмета:
solution.add(items.get(i — 1));
// если предмет выбран, то вычитаем его вес
capacity -= items.get(i — 1).weight;
ПРИМЕЧАНИЕ
И. при. построении. таблицы,. и. при. поиске. решения. вы. могли. заметить. увеличение.
и.уменьшение.итераторов.и.размера.таблицы.на.единицу..Это.сделано.для.удобства.
с.точки.зрения.программирования..Подумайте,.как.эта.задача.строится.снизу.вверх..
В.начале.решения.мы.имеем.дело.с.рюкзаком.нулевой.вместимости..Если.вы.подниме-
тесь.снизу.вверх.по.таблице,.то.поймете,.зачем.нужны.дополнительные.строка.и.столбец.

---

9.2. Задача коммивояжера
249
Вы.все.еще.в.замешательстве?.Таблица.9.1.—.это.то,.что.строит.функция.
knapsack()
..
Для.предыдущей.задачи.это.была.бы.довольно.большая.таблица,.так.что.вместо.
этого.рассмотрим.таблицу.для.рюкзака.вместимостью.3.фунта.и.трех.предметов:.
спичек.(1.фунт),.фонарика.(2.фунта).и.книги.(1.фунт)..Предположим,.что.эти.
предметы.оцениваются.в.5,.10.и.15.долларов.соответственно.