-
Notifications
You must be signed in to change notification settings - Fork 1
/
afl3.tex
171 lines (130 loc) · 6.44 KB
/
afl3.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
\documentclass[10pt,a4paper,danish]{article}
%% Indlæs ofte brugte pakker
\usepackage{amssymb}
\usepackage[danish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{booktabs}
\usepackage{graphicx}
%%Vi skal have ToDo-pakken fra Henne!
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\rhead{\today}
\rfoot{\thepage}
% Opsæt indlæsning af filer
\lstset{
language=Python,
extendedchars=\true,
inputencoding=utf8,
linewidth=\textwidth, basicstyle=\small,
numbers=left, numberstyle=\footnotesize,
tabsize=2, showstringspaces=false,
breaklines=true, breakatwhitespace=false,
}
%% Titel og forfatter
\title{Aflevering 3 \\Algoritmer og datastrukturer\\Forår/Sommer 2011}
\author{Naja Mottelson (vsj465)\\Søren Pilgård (vpb984)}
%% Start dokumentet
\begin{document}
%% Vis titel
\maketitle
\newpage
%% Vis indholdsfortegnelse
\tableofcontents
\newpage
%% Rapport, baby!
\section{a}
\subsection{Algoritme}
Vi ønsker at løse opgaven at give byttepenge (bestående af pennies, nickels, dimes og quarters)
for $n$ cents benyttende det mindst mulige antal mønter. En grådig algoritme til at gøre dette kan være
som følger: Hvis $n = 0$ gives 0 mønter. Hvis $n > 0$ findes den største
mønt med værdi $c$, $c<=n$, denne gives og derefter rekurserer vi ved at finde byttepenge for $n-c$ cents.
\subsection{Bevis}
For at bevise at denne algoritme giver den optimale løsning beviser vi indledningsvist at den
grådige egenskab gælder. I dette tilfælde vil det betyde at en given optimal løsning altid vil
indeholde en mønt med værdien $c$, hvor $c<=n$.
\\
For at gøre dette forestiller vi os en optimal løsning. Såfremt denne løsning er nødt til at indeholde
en mønt med værdien $c$ behøver vi ikke gøre mere. Ellers antager vi at løsningen ikke indeholder en
mønt med værdien $c$. Vi har følgende fire grænsetilfælde for $n$:
\begin{description}
\item[$1 <= n < 5$:] I dette tilfælde vil $c = 1$. Eftersom denne optimale løsning udelukkende må indeholde
pennies, må den nødvendigvis indeholde en mønt med værdien $c$.
\item[$5 <= n < 10$:] Her vil $c = 5$. Denne optimale løsning vil ligeledes udelukkende indeholde pennies,
eftersom vi antager at den ikke indeholder en nickel. Antallet af pennies vil dog nødvendigvis være større
end 5, hvorved vi kan erstatte de 5 pennies med en nickel og få en løsning med 4 færre mønter.
\item[$10 <= n < 25$:] Her vil $c = 10$. Vi antager at denne optimale løsning ikke indeholder en dime. En
en delmængde af de pennies og nickels den indeholder vil dog kunne summeres til 10, som så kan erstattes med
en dime og give en løsning med færre mønter (det specifikke antal færre mønter ligger imellem 1 og 9).
\item[$25 <= n$:] Her vil $c = 25$. Ligesom ovenfor antager vi at denne optimale løsning ikke indeholder
en quarter. Den værdi (som er skarpt større end $n$) som indeholder det færrest mulige antal mønter vil i
dette tilfælde være 3 dimes. Disse vil kunne erstattes af to dimes og en nickel og så give en optimal løsning
med færre mønter.
\end{description}
Således har vi vist at en optimal løsning altid indeholder det grådige valg ($c$). Køretid for denne
algoritme er $\Theta(k)$ hvor $k =$ antallet af mønter i en optimal løsning. Vi ved at $k <= n$, så algoritmen
er $O(n)$.
\section{b}
Vi har møntenhederne $c^0, c^1, c^2, \ldots c^k$ for heltallene $c > 1$ og $k >= 1$. En grådig
algoritme til at give byttepenge for $n$ cents kunne i dette tilfælde virke ved at finde den
møntenhed $c^j$ der passer på at $j = max(0 <= i <= k)$ hvor $c^i <= n$. Den returnerer en mønt
$c^j$ og rekurserer over underproblemet at give byttepenge for $n - n^j$.
\\
For at kunne føre beviset beviser vi først følgende lemma: Lad $a_i$ være antallet af mønter brugt
i en given optimal løsning. Da gælder at $a_i < c$.
\\
\emph{Bevis}: Hvis $a_i >= c$ for et $i$ hvor $0 <= i < k$ så kan vi forbedre løsningen ved at bruge
én mere mønt af enhed $ c^i+1$ og $c$ færre mønter møntenhed $c^i$. Vi vil i dette tilfælde få en
løsning med $c - 1$ færre mønter.
\\
Vi betragter nu en ikke-grådig løsning, som ikke benytter nogen mønter af møntenhed $c^j$ eller
højere. Lad den ikke-grådige løsning bruge $a_i$ mønter af møntenhed $c^i$ for $
i = 0, 1, \ldots j-1$.
\\
Vi kan, pr. ovenstående lemma, konkludere at en optimal løsning ikke kan indeholde mere end
$(c-1)$ af hver møntenhed. Således vil den maksimale værdi vi kan konstruere vha. mønter
af møntenhed $<= c^j-1$ kunne beskrives som $(c-1)c^0 + c-1)c^1 +c-1)c^2 + \ldots c-1)c^k$.
Vi ser at denne sumfølge kan skrives op på formen for geometriske serier (A.5 i CLRS):
$\displaystyle (c-1)\sum\limits_{i=0}^j-1 c^i = \frac{c^j - 1}{c -1} (c - 1)$
\\
\\
Vi ser endvidere at dette kan reduceres til
\\
\\
$\displaystyle (c-1)\sum\limits_{i=0}^j-1 c^i = c^j - 1$
\\
\\
Eftersom vi ved at $c^j <= n$, og således at $c^j - 1 < n$ kan vi ud fra ovenstående
konkludere at man ikke vil være i stand til at give byttepenge for $n$ cents udelukkende
vha. mønter af møntenhederne $c^0, c^1, c^2, \ldots c^j-1$. Dette betyder at den ikke-grådige
løsning ikke er optimal.
\\
Eftersom enhver algoritme som ikke inkluderer det grådige valg ($c^j$) må være suboptimal,
kan vi konkludere at den grådige løsning altid vil være optimal.
\section{c}
Fjerner vi 'nickel'-enheden fra mængden af enheder i denne opgave får vi en mængde af møntenheder
hvorpå den grådige strategi ikke giver en optimal løsning. Eksempel: $n = 30$. Her vil en grådig
algoritme give én quarter og fem pennies, hvor den optimale løsning ville have været 3 dimes.
\section{d}
Lad $num[j] =$ min. antal mønter vi skal bruge for at give byttepenge for j cents og de forskellige
møntenheder være $d_0, d_1, d_2 \ldots d_k$.
Hvis vi vidste at en optimal løsning indeholdt en møntenhed $di$, ville vi have
$num[j] = 1 + num[j - di]$.
Lad $den[j]$ være en møntenhed benyttet i en optimal løsning for at give byttepenge for $j$ cents.
Vores algoritme skal returnere num og den, da disse tabeller indeholder al den information vi
behøver for at udregne den optimale løsning.
Udkast til algoritme:
\begin{verbatim}
CHANGE(n, d, k)
for j <- 1 to n:
num[j] <- infinity
for i <- 1 to k:
if j >= $d_i$ and 1 + num[j - $d_i$] < num[j]
then num[j] <- 1 + num[j - $d_i$]
den[j] <- $d_i$
return num, den
\end{verbatim}
\end{document}