О блоге

Рейтинг
0.00
голосов: 0
Будем учиться решать стандартные задачи шаблонами.

Администраторы (2)

Модераторы (0)

Модераторов здесь не замечено

Читатели (3)

Задача о рюкзаке

Возможная формулировка задачи (из Олимпиады 26.05.2012):
Вася решил в очередной раз съездить до деревни Y. Но путь до нее не простой, поэтому Васе необходимо запастись едой. При этом Вася знает, что, если его груз станет тяжелее Wmax кг, ему будет ехать очень не комфортно, и он не получит никакого удовольствия от этой поездки.
Открыв холодильник, Вася увидел там много еды, для которой известна ее энергетическая ценность и вес. Помогите Васе выбрать, что брать с собой так, чтобы суммарная энергетическая ценность еды была максимальна.

Формат входных данных
В первой строке даны два числа вещественное Wmax — максимальный вес груза Васи (1 <= Wmax <= 1000 и целое n (1 <= n <= 15) — количество единиц еды, которая есть в холодильнике. В последующих n строках даны по 2 числа целое c и вещественное w (1 <= c <= 1000, 1 <= w <= 1000) — энергетическая ценность и вес текущей единицы еды соответственно.
Все вещественные числа в задаче даны с точностью 10^-2.

Формат выходных данных
Выведите максимальную возможную энергетическую ценность.

Пример
Ввод 1
10.00 4
3 5.00
6 7.00
2 4.00
1 1.00
Вывод 1
7

Ввод 2
23.70 6
10 15.80
5 3.70
23 7.70
13 10.10
8 4.30
20 17.70
Вывод 2
44
Возможное решение:
program P_Rukzak;
{$APPTYPE CONSOLE}
uses
  SysUtils;

var MaxWeight,TempWeight: real;
    TotalValue,TempValue,Quantity,i,j,QuantityVariants: word;
    Weight: array[1..15] of real;
    Value: array[1..15] of word;
begin
  Assign(input, 'input.txt');   reset(input);
  Assign(output, 'output.txt'); rewrite(output);
  readln(MaxWeight,Quantity);    // считываем максимальный вес
                                 // считываем количество единиц
  for i:=1 to Quantity do
    readln(Value[i],Weight[i]);  // считываем данные про еду

  QuantityVariants:=1 shl Quantity;  // количество разных наборов
  TotalValue:=0;  // искомая сумма ценностей элемнтов

  for i:=1 to QuantityVariants-1 do // перебираем наборы элементов
  begin // ноль можно и пропустить

    TempWeight:=0;  // вес текущего набора
    TempValue:=0;   // ценность текущего набора

    for j:=0 to Quantity-1 do  // перебираем элементы
    begin
      x:=(i and (1 shl j)) shr j; // =1, если присутсвует в наборе
      TempWeight:=TempWeight+x*Weight[j+1]; // текущий суммарный вес
      TempValue:=TempValue+x*Value[j+1];    // текущий суммарная ценность
    end;

    if (TempWeight<=MaxWeight) and (TempValue>TotalValue)
      then TotalValue:=TempValue;

  end;

  write(TotalValue);

  close(input); close(output);
end.

Описание подхода к решению:
Как не крутил не смог далеко отойти от решения Вадима Шилова (организатор Олимпиады) — просто это решение, видимо, близко к оптимальному… Комментируйте эти опции:
— в каких сложных ситуациях это решение не подойдет,
— что ещё можно сократить, чтобы непосредственно на Олимпиаде можно было бы использовать шаблон с минимальной длиной кода,
— как лучше писать, чтобы шаблон этот был понятный и несложно настраиваемый под конкретную задачу…
Суть «Задачи о рюкзаке».
Иногда пишут «о ранце». Имеется n предметов, каждому из которых назначена ценность Cj>0 и указан вес Wj>0, где j=1,2,..,n. Имеется ранец, вместимость которого ограничена — R. По понятным причинам — сумма всех Wj>R, то есть все предметы в ранец никак не положить. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью.
Суть решения: перебор всех наборов с проверкой двух условий:
1) вес набора <= вместимости рюкзака
2) ценность текущего набора > текущей максимальной ценности.
Набор — это любым образом представленный способ обозначения — какие предметы из общего списка предполагается положить в ранец (есть), а какие в этот раз не будем брать (нет). Те, которые берём обозначим 1, которые не берем — 0. Например, всего есть 4 предмета, мы берем первый, третий и четвертый — этот набор можно обозначить так — 1011. А сколько всего наборов может быть? Очевидно, что два в степени количество предметов, то есть для 4-х предметов наборов будет 16, для 10 — 1024, а для 15 — 32768 (под завязку стандартного интеджера, если считать от нуля).
Формула для подсчета веса: Wсуммарный=Xj*Wj.
Формула для подсчета ценности: Cсуммарная=Xj*Cj.
Где Xj=0, если предмета нет в наборе и Xj=1, если предмет есть.
Видимо в данном конкретном случае нет необходимости как-то сокращать мощность (количество исследуемых наборов) перебора, так как количество наборов сравнительно невелико.
В подобных задачах встречаются разнообразности — бывало мне когда-то (в 1997), при значительном числе наборов и требовании быстрого поиска решения, использовать методы оптимизации — это как правило методы приближенного решения, то есть когда в минимальные сроки нужно найти приемлемое решение (дается допуск) — вспоминается «Метод ветвей и границ». Но это уже не данная обсуждаемая задача. Это отметил тут, чтобы не забыть — может быть и это обсудим…
Возвращаюсь. Итак обычное решение при полном переборе тривиально:
1) запускаем внешний цикл по i с известным количеством повторов (так что подойдет for), количество итераций цикла есть количество разных наборов — QuantityVariants=2^количество предметов,
2) каким-то образом номеру набора i ставим в соответсвие его обозначение нулями и единицами — характеризующими отсутствие или наличие предметов в наборе (можно, например, просто номер набора i переводить в двоичное представление — был десятичный номер набора i=11, а стал — 1011 в двоичной системе) — по сути это будет маска — это может быть также и массив (где количество элементов массива = количеству предметов), в котором хранятся те же нули и единицы (кому как понятнее)
3) запускаем внутренний цикл по j — этот цикл по количеству предметов
4) если j-тый предмет есть в текущем наборе i, то суммируем его ценность и вес
5) проверяем сложное условие (вес набора <= вместимости рюкзака) and (ценность текущего набора > текущей максимальной ценности), при его истинности назначаем ценность текущего набора ----> текущей максимальной ценностью.
Вот и весь алгоритм. Можно поразному сделать пункт 2 (выше указал), но приведенный вариант, по всей видимости, наиболее компактный. Можно немного изменить пункт 4, вот пример:
for j:=0 to Quantity-1 do  // перебираем элементы
  if (i and (1 shl j))>0 then // проверяем их присутсвие в наборе
  begin
    TempWeight:=TempWeight+Weight[j+1]; // текущий суммарный вес
    TempValue:=TempValue+Value[j+1];    // текущий суммарная ценность
  end;

Можно найти количество разных наборов не так: QuantityVariants:=1 shl Quantity; а как два в степени Quantity: QuantityVariants:=IntPower(2,Quantity);
Напоминаю, что сдвиг влево shl и вправо shr — побитовые операции и, если m:=1 shl 3; то из такого двоичного числа 0001, получиться такое 1000, то есть из 1 получиться 8, и кроме того это означает, что так можно двойку возводить в степень, сдвинув нужное количество раз влево…
Что тут происходит: x:=(i and (1 shl j)) shr j;?
шаг 1: единицу двигаем влево j раз (1 shl j), чтобы получить её в позиции очередного предмета
шаг 2: потом её умножаем эндом на i (i and (1 shl j)), чтобы понять есть ли она в текущем наборе, если есть, то получим число >0 (1 или 2 или 4 или 8 и т.д., смотря в какой позиции)
шаг 3: сдвигаем обратно вправо, чтобы из «1 или 2 или 4 или 8 и т.д.» сделать просто 1 (ну или ноль) и использовать её в формулах: Wсуммарный=Xj*Wj и Cсуммарная=Xj*Cj.

Почему нужна эта тема?

Почему в закрытом и что тут делать?
В закрытом блоге — так как нам не нужно лишнего мусора от случайных участников, но самое главное, чтобы наработками не пользовались конкуренты.
— по поводу Олимпиады 26.05.2012:
— коротко повторю мысль — часть задач очень похожа на те, что я предлагал, часть — стандарты
— я понимаю, что у всех в жизни есть и свои дела, но решать стандаты надо обязательно научиться
— считаю, что основная причина слабого выступления: мало личных затрат времени на подготовку, к примеру, турнир подготовленный Александром Турнир «Подготовка (23.04.2012)» кто то дома решал?
— только два игрока оставляют регулярно свои комментарии и версии программ по задачам, публикуемым на нашем форуме — олимпиада показала, что подготовка «наскоком» неэффективна
— не уверен, прочитают ли этот тезис больше половины игроков, но всё же просьба от меня: поактивнее участвуйте в работе форума «Команда ФПИ по программированию» и смежных тем, оставляйте комментарии, делитесь наработками, в том числе совершенными ошибками в процессе решения…
— как я и раньше предполагал так и продолжаю — за 3 часа можно было бы решить командой нашего уровня 4-6 стандартных задач уровня сложности «Энергетическая ценность»
— судя по итоговой таблице «команда 8 место» решила только 2 задачи, а «команда 3 место» — 6 задач — вот в этом диапазоне при предложенных задачах должны были оказаться и мы — сложности могли быть только при доводке готовых программ до того состояния, чтобы их приняла система формализованной проверки (типа на каких то тестах не проходит и т.п.)
— я предлагаю всем игрокам поучаствовать в наполнении этой темы — как и у вас моё личное время тоже ограничено и я не смогу охватить многое…
— тут публикуем, обсуждаем и оптимизируем только шаблоны программ для решения задач, которые можно свести к стандартным