\Section{Динамическое программирование}{16 октября}{Винниченко Максим}
\Subsection{Рюкзак}

	\Subsubsection{задача}
	
	Дано множество предметов $a_1, a_2, \dots, a_n$
	
	$a_i > 0,\ W > 0$
	
	Нужно выбрать подмножество: $\sum a_i = W$
	
		\begin{enumerate}
			\item NP-hard
			\item $n \cdot 2^n$
			\item $\exists$ решения за $2^{n/2}$
			
			(meet in middle)
		\end{enumerate}
		
	\Subsection{решение за O(nW)}
	
	Просмотрели первых $i$, взяли подмножество суммы $w$	
	
	\begin{tabular}{ll}
	$is[i, w]$ & $\rightarrow$ $is[i + 1, w + a[i + 1]]$ \\
	           & $\rightarrow$ $is[i + 1, w]$ \\
	
	\end{tabular}
	
	\begin{code}
		is[0,0] = 1:
		for i = 1..n-1:
		  for w = 0..W:
		    if is[i, w]:
		      is[i + 1, w] = 1
		      is[i + 1, w + a[i]] = 2
	
	\end{code}
	
	\Subsubsection{восстановление ответа}

	\begin{code}
		i = 1, w = W
		ans = []
		while (i > 0):
		    if (is[i][W] == 2):
		         W -= a[i]
		         ans.append(a[i])
		    i--
	\end{code}
	
	\Subsubsection{оптимизируем память: храним 1-2 посл. строчек}

	\begin{code}
	    for i = 0..n-1:
	      for w = W-a[i]..1:       // `for w = 0..W-a[i] не верно!!!`
	        if (is[w]):
	        is[w + a[i]] = 1
	\end{code}
	
		\Subsubsection{код с bitset}
		
		\begin{code}
			bitset<W + 1> is;
			is[0] = 1;
			for (int i = 0; i < n; i++) {
			  is |= is << a[i];
			}
		\end{code}

		$Memory=\Theta(\frac{W}{b}), \quad b = 64$
		
		$Time=\Theta(\frac{n \cdot W}{b})$
		
	\Subsubsection{Востановление ответа c O(W) памяти}
	
	$last[w]$ - номер последнего предмета в ответе для $w$
	\begin{code}
		last = [0, 0, ...]
		last[0] = -1
		for i = 0..i-1:
		  for w = W-a[i]..0:
		    if (last[w] != 0 and last[w + a[i]] == 0):
		      last[w + a[i]] = i + 1 
		
		w = W
		while(w != 0):
		  i = last[w] - 1
		  w -= a[i], res[i] = 1
	\end{code}
	
	для каждого w хранится наименьший номер последнего элемета
	  
   $\\ $	  
	  
   //для рюкзака со стоимостями такой способ восстановления ответа не верен
	  
\Subsection{Алгоритм Хиршберга}

	\Subsubsection{НОП}
	
	даны стороки a, b
	
	$dp[i,j]$ - НОП для $a[:i]$ и $b[:j]$
	\begin{code}
		relax(&x, y):
			x = max(x, y)
	
		lcs(a,b):
			//`тут должна быть инициализация dp нулями`
			
			for i = 0..len(a):
				for j = 0..len(b):
					relax(dp[i+1,j], dp[i,j])
					relax(dp[i,j+1], dp[i,j])
					if a[i] == b[j]:
						relax(dp[i,j+1],dp[i,j] + 1)
						
			ans = str()	        
	        i = len(a)
	        j = len(b)
	        while (i > 0 or j > 0):	`восстановление ответа`
	            if (dp[i,j] == dp[i-1,j]):
	            	i--
	            else if (dp[i,j] == dp[i,j-1]):
	            	j--
	            else if (dp[i,j] == dp[i-1,j-1] + 1):
	            	ans = a[i] + ans
	            	i--, j--
	        ans = ans.reverse()
	        return ans
	\end{code}

	\Subsubsection{НОП с восстановлением ответа и O(n + m) памяти}
	
	\begin{code}
	solve(la, ra, lb, rb):
    	if (min(ra - la, rb - lb) <= 1):
        	return lcs(a[la:ra], b[lb:rb]) //`длина одной строк <= 1, lcs = общий символ`
    		
    	// `надо хранить только 2 последние строчки dp`
    	for i = la..ra:
        	for j = lb..rb:
            	relax(dp[i,j], dp[i,j-1])
           		relax(dp[i,j], dp[i-1,j])
            	if (i > la and j > lb and a[i - 1] == b[j - 1]):
                	relax(dp[i,j], dp[i-1,j-1] + 1)
            	if (i == (la + ra) / 2):
                	dp[i,j].second = j
                	
    	mb = dp[ra,rb].second;
    	return solve(la, ma, lb, mb) + solve(ma, ra, mb, rb)
    		
    solve(0, len(a), 0, len(b)) //`запуск`
	\end{code}
	
	Хотим найти НОП(a,b) 
	\begin{itemize}
	\item Пусть $min(len(a), len(b)) > 1$, ma = len(a) / 2. 
	
	\item Находим такую клетку $dp[ma,mb]$, что через неё пройдёт восстановление ответа. 
	
	\item решаем для ($a[:ma]$ и $b[:mb]$) + ($a[ma:]$ и $b[mb:]$). 
	\end{itemize} 
	
	$\\ $	
	
	Корректность: 
	\begin{itemize}
		\item восстановление ответа проходит через хотя бы 1 клетку из dp[ma,*]
		\item $\exists j,\ $ НОП(a,b) = НОП($a[:ma]$ и $b[:j]$) + НОП($a[ma:]$ и $b[j:]$)
		\item j = mb подойдёт. (буквы в НОП соотв переходам $dp[i,j] \rightarrow dp[i-1,j-1]$ в восстановлении ответа)
	\end{itemize}
	
	$\\ $	
	
	Время: $\mathcal{O}(nm),\ n = len(a),\ m = len(b)$
	
	$T(1, m) = m,\ T(n, 1) = n$	
	
	$T(n,m) \le (3n-1)(3n-1)-2$
	
	$T(n, m) \le (n + 1)(m + 1) + T(\frac{n}{2}, m - i) + T(\frac{n}{2}, i) = (n + 1)(m + 1) + (\frac{3n}{2}-1)(3m-2)-4$
	
	$\\ $	
	
	Память: $M = $ dp + ответ + стек рекурсии = $\mathcal{O}(2(m+1))$ + $\mathcal{O}(n) + o(n)$ = $O(n + m)$
