\section{Задача N. <<Unknown>>}

\begin{frame}[t]{Задача N. <<Unknown>>}

  \begin{center}
    \LARGE Задача N. <<Unknown>>
  \end{center}

  \begin{itemize}
    \item Идея задачи --- Xxx Yyy
    \item Подготовка тестов --- Xxx Yyy
    \item Разбор задачи --- Xxx Yyy
  \end{itemize}
\end{frame}

\subsection{Постановка задачи}

\begin{frame}[t]{Дискретная задача о рюкзаке}
Входные данные:
\begin{itemize}
	\item Есть $n$ вещей и рюкзак вместимостью $s$
	\item Вещь с номером $i$ характеризуется размером (весом) $w_i$
	 и ценой $c_i$
\end{itemize}
Нужно выбрать некоторое подмножество вещей так, чтобы:
\begin{itemize}
	\item Суммарный размер выбранных вещей не превосходил $s$
	\item Суммарная цена выбранных вещей была как можно больше
\end{itemize}
Дополнительное условие: $w_i$ "--- положительные целые числа.
\end{frame}

\subsection{Варианты постановки задачи}

\begin{frame}[t]{Варианты постановки задачи}
\begin{itemize}
	\uncover<1->%
	{%
	\item Нужно набрать как можно больше вещей ($c_i = 1$) \\
	}%
	\uncover<2->%
	{%
	 \textit{Решается жадным алгоритмом:
	  отсортируем вещи по весу и будем брать, начиная с самой маленькой,
	  пока они помещаются}
	}%
	\uncover<3->%
	{%
	\item Цен нет, нужно набрать как можно больший вес ($c_i = w_i$) \\
	}%
	\uncover<4->%
	{%
	 \textit{Решается аналогично исходной постановке}
	}%
	\uncover<5->%
	{%
	\item Вещей каждого типа не одна, а сколько угодно \\
	}%
	\uncover<6->%
	{%
	 \textit{Решается аналогично исходной постановке}
	}%
\end{itemize}
\end{frame}

\subsection{Пример}

\begin{frame}[t]{Пример}%
\begin{center}%
        $n = 4$ \\
        $s = 6$ \\
        \medskip
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		$i$   & \hl<3,5>{$1$} & \hl<2-3>{$2$} & \hl<3,6>{$3$} & \hl<2,5-6>{$4$} \\
		\hline
		$w_i$ & \hl<3,5>{$1$} & \hl<2-3>{$2$} & \hl<3,6>{$3$} & \hl<2,5-6>{$4$} \\
		\hline
		$c_i$ & \hl<3,5>{$2$} & \hl<2-3>{$3$} & \hl<3,6>{$5$} & \hl<2,5-6>{$7$} \\
		\hline
	\end{tabular}
        \medskip
	\\
	\only<2>%
	{%
		Оптимальное решение: \\ 
		Выберем вещи с номерами $2$ и $4$. \\
		Суммарный вес равен $2 + 4 = 6$. \\
		Суммарная цена равна $3 + 7 = 10$. \\
	}%
	\only<3>%
	{%
		Ещё одно оптимальное решение: \\ 
		Выберем вещи с номерами $1$, $2$ и $3$. \\
		Суммарный вес равен $1 + 2 + 3 = 6$. \\
		Суммарная цена равна $2 + 3 + 5 = 10$. \\
	}%
	\only<4>%
	{%
		Всего есть $2 \cdot 2 \cdot 2 \cdot 2 = 16$ вариантов
		решения: \\
		каждую вещь можно независимо от других либо взять,
		либо не взять. \\
	}%
	\only<5>%
	{%
		Некоторые решения неоптимальны: \\
		Выберем вещи с номерами $1$ и $4$. \\
		Суммарный вес равен $1 + 4 = 5$. \\
		Суммарная цена равна $2 + 7 = 9$. \\
		Заметим, что в этом решении не добавить ещё одну вещь. \\
	}%
	\only<6>%
	{%
		Некоторые решения невозможны: \\
		Выберем вещи с номерами $3$ и $4$. \\
		Суммарный вес равен $3 + 4 = 7 > s$. \\
	}%
\end{center}
\end{frame}

