\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\usepackage{t1enc}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}

\usepackage{tikz}
\usetikzlibrary{shapes.symbols}

\usepackage[a4paper, left=20mm, right=20mm, top=20mm, bottom=20mm]{geometry}

\usepackage{datetime}

\usepackage{multicol}

\setlength{\parindent}{1.5em}
\setlength{\parskip}{1em}
\renewcommand{\baselinestretch}{1.2}

\title{Bonyolultságelmélet V. házi feladat \\
\large Approximálás
}

% Ide írd a neved és a Neptun kódod. A \\ a sortörést jelenti LaTeX-ben.
\author{Kaposvári Dániel \\ PCI6GG}

\date{\today ~ \currenttime}

\begin{document}

\maketitle

\begin{minipage}{20cm}

% A képletet dollárjelek közé helyezd.
${\bf\textsc{Hátizsák}}$
		\begin{itemize}
			\item {\bf Input}: $(w_i, c_i)$ pozitív egész (súly, érték) számpárok egy $i= 1, ..., n$ sorozata \\
			és egy $W$ összkapacitás.
			\item {\bf Output}: A tárgyak egy $I \subseteq {1, ..., n}$ részhalmaza, melyre a $\sum_{i \in I}w_i \le W$, \\
			és ezen belül $c(I)=\sum_{i \in I}c_i$ összérték maximális.
		\end{itemize}
\end{minipage}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%% A PÉLDÁT TÖRÖLD KI! %%%%%%%%%%%%

\noindent % az automatikus első sor behúzást  a következő bekezdésre
\textbf{1. Példa:} Hajtsd végre a tanult approximáló algoritmust $\textbf{k=1}$ esetén a $\textsc{Hátizsák}$ probléma következő inputján! A kapott eredmény alapján mit tudsz elmondani az optimum értékéről?

$W = 120$, a lehetséges tárgyak:

\begin{center}
\begin{tabular}{ c|c|c|c|c|c } 
  & A & B & C & D & E \\
 \hline
 Súly & 80 & 20 & 70 & 50 & 10 \\
 \hline
 Érték & 120 & 35 & 140 & 60 & 10
\end{tabular}
\end{center}

\noindent
\textbf{Megoldás:}
A mohó algoritmus szerinti $\frac{c_i}{w_i}$ arányok és a sorrend:

\begin{center}
\begin{tabular}{ c|c|c|c|c|c } 
 Tárgyak sorrendben & C & B & A & D & E \\
 \hline
 $\frac{c_i}{w_i}$ arányok & $\frac{140}{70} = 2$ & $\frac{35}{20} = 1.75$ & $\frac{120}{80} = 1.5$ & $\frac{60}{50} = 1.2$ & $\frac{10}{10} = 1$ \\
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ c|c|c|c } 
Fix tárgyak & Mohó tárgyak & Súlyok & Értékek \\
\hline
A & B, E & 80 + 20 + 10 = 110 &  120 + 35 + 10 = 165 \\
\hline
B & C, E & 20 + 70 + 10 = 100 & 35 + 140 + 10 = 185 \\
\hline 
C & B, E & 70 + 20 + 10 = 100 & 140 + 35 + 10 = 185 \\
\hline 
\textbf{D} & \textbf{C} & \textbf{50 + 70 = 120} & \textbf{60 + 140 = 200} \\
\hline 
E & C, B & 10 + 70 + 20 = 100 & 10 + 140 + 35 = 185 
\end{tabular}
\end{center}

Az algoritmus szerint a választásunk az $I= \{C, D\}$ halmaz, amellyel $c(I) =200$ hasznot tudunk elérni. Mivel a futtatott algoritmus $1+\frac{1}{k} = 1+\frac{1}{1}$, azaz 2-approximáló, ez azt is jelenti, hogy az optimum értéke legfeljebb 400 lehet.

% gyakoribb jelölések:

% \quad parancs tabot tesz az egyenletbe
% \begin{env} \end{env} között lehet különböző előre- vagy általunk definiált környezetben dolgozni.
% \\ a sortörés. Aligned env.-ben a \\[] megadható térköz. Szintén az aligned env.-ben a & jellel lehet egymás alá igazítani a sorokat.
% Matekos környezetben, amit $közé$ egysorban, $$közé$$ külön kitéve vagy az equation environmentben lehet megoldani a ~ jel a space. 
% a többire a minta kódokat fent láthatod
% ha valamilyen más szimbólum írását nem tudod, akkor a google segít

% oldaltörés
%\newpage

%%%%%%%%%%%%% A PÉLDA VÉGE %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newpage

\noindent
\textbf{Feladat:} Hajtsd végre a tanult approximáló algoritmust $\textbf{k=2}$ esetén a $\textsc{Hátizsák}$ probléma következő inputján! A kapott eredmény alapján mit tudsz elmondani az optimum értékéről?

\bigskip

$W = 120$, a lehetséges tárgyak:

\begin{center}
\begin{tabular}{ c|c|c|c|c|c } 
  & A & B & C & D & E \\
  \hline
 Súly & 40 & 50 & 100 & 45 & 25 \\
 \hline
 Érték & 70 & 75 & 200 & 45 & 30 \\

 
\end{tabular}
\end{center}

% IDE ÍRD A MEGOLDÁSOD

\noindent
\textbf{Megoldás:}
A mohó algoritmus szerinti $\frac{c_i}{w_i}$ arányok és a sorrend:

\begin{center}
\begin{tabular}{ c|c|c|c|c|c } 
 Tárgyak sorrendben &  &  &  &  &  \\
 \hline
 $\frac{c_i}{w_i}$ arányok & $\frac{}{} = $ & $\frac{}{} = $ & $\frac{}{} = $ & $\frac{}{} = $ & $\frac{}{} = $
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ c|c|c|c } 
Fix tárgyak & Mohó tárgyak & Súlyok & Értékek \\
\hline 
&        &      &      \\
\hline 
&        &      &      \\
\end{tabular}
\end{center}

Az algoritmus szerint a választásunk az $I= \{ ??? \}$ halmaz, amellyel $c(I) =???$ hasznot tudunk elérni. Mivel a futtatott algoritmus ???-approximáló, ez azt is jelenti, hogy az optimum legfeljebb ???.


\end{document}
