Difference between revisions of "TADM2E 1.5"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
Line 1: Line 1:
<p>First-fit algorithm counterexample:</p>
+
<p>First-fit algorithm counterexample:</p>
&lt;p&gt;
+
<p>
&lt;math&gt;S = \{1, 2, 3\}&lt;/math&gt;
+
<math>S = \{1, 2, 3\}</math>
&lt;br/&gt;
+
<br/>
&lt;math&gt;T = 5&lt;/math&gt;
+
<math>T = 5</math>
&lt;/p&gt;
+
</p>
  
&lt;p&gt;Best-fit algorithm counterexample:&lt;/p&gt;
+
<p>Best-fit algorithm counterexample:</p>
&lt;p&gt;
+
<p>
&lt;math&gt;S = \{1, 2, 3\}&lt;/math&gt;
+
<math>S = \{1, 2, 3\}</math>
&lt;br/&gt;
+
<br/>
&lt;math&gt;T = 5&lt;/math&gt;
+
<math>T = 5</math>
&lt;/p&gt;
+
</p>
  
&lt;p&gt;Largest to smallest algorithm counterexample:&lt;/p&gt;
+
<p>Largest to smallest algorithm counterexample:</p>
&lt;p&gt;
+
<p>
&lt;math&gt;S = \{4, 3, 2\}&lt;/math&gt;
+
<math>S = \{4, 3, 2\}</math>
&lt;br/&gt;
+
<br/>
&lt;math&gt;T = 5&lt;/math&gt;
+
<math>T = 5</math>
&lt;/p&gt;
+
</p>
 
----
 
----
&lt;p&gt;Another counterexample:&lt;/p&gt;
+
<p>Another counterexample:</p>
If &lt;math&gt;t=11&lt;/math&gt;, the solution would be the subset &lt;math&gt;\{2, 9\}&lt;/math&gt; or &lt;math&gt;\{1, 10\}&lt;/math&gt; which none of the algorithms found.
+
If <math>t=11</math>, the solution would be the subset <math>\{2, 9\}</math> or <math>\{1, 10\}</math> which none of the algorithms found.
  
  
 
Using first-fit algorithm (left to right)
 
Using first-fit algorithm (left to right)
{| class=&quot;wikitable&quot;
+
{| class="wikitable"
 
|-
 
|-
 
! Item added
 
! Item added
! Subset of &lt;math&gt;S&lt;/math&gt;
+
! Subset of <math>S</math>
 
! Sum
 
! Sum
 
|-
 
|-
 
| 1
 
| 1
| &lt;math&gt;\{1\}&lt;/math&gt;
+
| <math>\{1\}</math>
| 1 &lt; 11
+
| 1 < 11
 
|-
 
|-
 
| 2
 
| 2
| &lt;math&gt;\{1, 2\}&lt;/math&gt;
+
| <math>\{1, 2\}</math>
| 3 &lt; 11
+
| 3 < 11
 
|-
 
|-
 
| 5
 
| 5
| &lt;math&gt;\{1, 2, 5\}&lt;/math&gt;
+
| <math>\{1, 2, 5\}</math>
| 8 &lt; 11
+
| 8 < 11
 
|-
 
|-
 
| 9
 
| 9
| &lt;math&gt;\{1, 2, 5, 9\}&lt;/math&gt;
+
| <math>\{1, 2, 5, 9\}</math>
| 17 &gt; 11
+
| 17 > 11
 
|}
 
|}
  
  
 
Using best-fit algorithm (smallest to largest)
 
Using best-fit algorithm (smallest to largest)
{| class=&quot;wikitable&quot;
+
{| class="wikitable"
 
|-
 
|-
 
! Item added
 
! Item added
! Subset of &lt;math&gt;S&lt;/math&gt;
+
! Subset of <math>S</math>
 
! Sum
 
! Sum
 
|-
 
|-
 
| 1
 
| 1
| &lt;math&gt;\{1\}&lt;/math&gt;
+
| <math>\{1\}</math>
| 1 &lt; 11
+
| 1 < 11
 
|-
 
|-
 
| 2
 
| 2
| &lt;math&gt;\{1, 2\}&lt;/math&gt;
+
| <math>\{1, 2\}</math>
| 3 &lt; 11
+
| 3 < 11
 
|-
 
|-
 
| 5
 
| 5
| &lt;math&gt;\{1, 2, 5\}&lt;/math&gt;
+
| <math>\{1, 2, 5\}</math>
| 8 &lt; 11
+
| 8 < 11
 
|-
 
|-
 
| 9
 
| 9
| &lt;math&gt;\{1, 2, 5, 9\}&lt;/math&gt;
+
| <math>\{1, 2, 5, 9\}</math>
| 17 &gt; 11
+
| 17 > 11
 
|}
 
|}
  
  
 
Using largest to smallest
 
Using largest to smallest
{| class=&quot;wikitable&quot;
+
{| class="wikitable"
 
|-
 
|-
 
! Item added
 
! Item added
! Subset of &lt;math&gt;S&lt;/math&gt;
+
! Subset of <math>S</math>
 
! Sum
 
! Sum
 
|-
 
|-
 
| 10
 
| 10
| &lt;math&gt;\{10\}&lt;/math&gt;
+
| <math>\{10\}</math>
| 10 &lt; 11
+
| 10 < 11
 
|-
 
|-
 
| 9
 
| 9
| &lt;math&gt;\{9, 10\}&lt;/math&gt;
+
| <math>\{9, 10\}</math>
| 19 &gt; 11
+
| 19 > 11
 
|}
 
|}
  
  
 
[[introduction-TADM2E|Back to ''Introduction ...'']]
 
[[introduction-TADM2E|Back to ''Introduction ...'']]

Revision as of 18:22, 11 September 2014

First-fit algorithm counterexample:

$ S = \{1, 2, 3\} $
$ T = 5 $

Best-fit algorithm counterexample:

$ S = \{1, 2, 3\} $
$ T = 5 $

Largest to smallest algorithm counterexample:

$ S = \{4, 3, 2\} $
$ T = 5 $


Another counterexample:

If $ t=11 $, the solution would be the subset $ \{2, 9\} $ or $ \{1, 10\} $ which none of the algorithms found.


Using first-fit algorithm (left to right)

Item added Subset of $ S $ Sum
1 $ \{1\} $ 1 < 11
2 $ \{1, 2\} $ 3 < 11
5 $ \{1, 2, 5\} $ 8 < 11
9 $ \{1, 2, 5, 9\} $ 17 > 11


Using best-fit algorithm (smallest to largest)

Item added Subset of $ S $ Sum
1 $ \{1\} $ 1 < 11
2 $ \{1, 2\} $ 3 < 11
5 $ \{1, 2, 5\} $ 8 < 11
9 $ \{1, 2, 5, 9\} $ 17 > 11


Using largest to smallest

Item added Subset of $ S $ Sum
10 $ \{10\} $ 10 < 11
9 $ \{9, 10\} $ 19 > 11


Back to Introduction ...