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

Возможная формулировка задачи (из Олимпиады 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.

Комментарии (3) свернуть  |  развернуть

0
Я бы даже сказал, что задачу о рюкзаке можно свести к простому перебору всех возможных вариантов с использованием двоичного представление того или иного набора.
0
Т.е. в самом общем виде все решение задачи сводится к знанию следующего алгоритма:

// ...
VariantsCount := 1 shl ElementsCount;
for VariantIndex := 1 to VariantsCount - 1 do
  // ...
  for ElementIndex := 0 to ElementsCount - 1 do
    if (VariantIndex and (1 shl ElementIndex)) shr ElementIndex = 1 then
      begin
        // Обработка элемента в наборе...
      end;
// ...
+1
— да, чуть не забыл основную цель закрытого блога: формируем банк шаблонов, максимально простых для понимания и запоминания
— прямо сейчас приснился шаблон, приведенный Александром :) — увидел, что можно покороче:
// ...
VariantsCount := 1 shl ElementsCount;
for VariantIndex := 1 to VariantsCount - 1 do
  // ...
  for ElementIndex := 0 to ElementsCount - 1 do
    if (VariantIndex and (1 shl ElementIndex)) > 0 then
      begin
        // Обработка элемента в наборе...
      end;
// ...

Прокомментировать