アクティビティの選択に関する質問

アクティビティ選択問題

問題の説明:

n 個のアクティビティ E={1,2,…,n} のセットがあり、それぞれが同じリソースの使用を必要とするものとします。講演会場などとして利用でき、同時に利用できるアクティビティは1つだけです。各アクティビティ i には、リソースの使用を必要とする開始時刻 si と終了時刻 fi があり、si

。

この図から、S には 11 個のアクティビティがあることがわかります。相互に互換性のある最大のアクティビティ サブセットは、{a₁、a₄ です。 、a₈、a11,} および {a₂、a₄、a₉、a₁₁ }。

2. 動的計画法解法プロセス

(1) アクティビティ選択問題の最適部分構造

部分問題の定義解空間 S_ij は S の部分集合であり、すべての結果は互いに互換性があります。つまり、各アクティビティは a_i が終了した後に開始され、a_j が開始する前に終了します。

議論とその後の計算を容易にするために、2 つの架空のアクティビティ a₀ と a_{n 1 を追加します。}ここで f₀=0、s_{n 1}=∞。

結論: i≥j のとき、S_ij は空集合です。

アクティビティが終了時刻までに単調増加するように順序付けされている場合、部分問題空間を使用して、S_ij (0≤iij はすべて空集合です。

最適な部分構造は次のとおりです。 S_ij の最適解 A_ij にアクティビティ a_k が含まれていると仮定します。 _ik の解 A_ik と S_kj の解 A_kj は最適でなければなりません。

アクティビティ a_k を通じて問題を 2 つのサブ問題に分割します。次の式で S_{ijij >。}

(2) 再帰的解法

c[i][j] を S

ij

とする>k _{の最大の互換性のあるサブセット内のアクティビティの数は、S}ij _{の最大の互換性のあるサブセットで使用され、次に問題 S}ik _{および S}kj _{も使用されるため、 c[i][j] = c[i][k] c[k][j] 1 を取得できます。} i≥j の場合、S_ij は空集合でなければなりません。それ以外の場合、S_ij は上記の式に従って計算する必要があります。 a

k

の場合、Sij _{は空ではありません (この時点では f}i_≤sk _{および f}k を満たします) _≤sj_{)、そのような}k _{が見つからない場合、S}ij _{は空集合です。} c[i][j] の完全な計算式は次のとおりです:

個人テスト コード:

コードを表示

以下は貪欲メソッドのコードです:

<span style="color: #008080;"> 1</span> #include <bits/stdc++.h><span style="color: #008080;"> 2</span> <span style="color: #0000ff;">#define</span> max_size 10010<span style="color: #008080;"> 3</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> s[max_size];</span><span style="color: #008080;"> 4</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> f[max_size];</span><span style="color: #008080;"> 5</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> c[max_size][max_size];</span><span style="color: #008080;"> 6</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> ret[max_size][max_size];</span><span style="color: #008080;"> 7</span> <span style="color: #008080;"> 8</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;</span><span style="color: #008080;"> 9</span> <span style="color: #008080;">10</span> <span style="color: #0000ff;">void</span> DP_SELECTOF(<span style="color: #0000ff;">int</span> *s,<span style="color: #0000ff;">int</span> *f,<span style="color: #0000ff;">int</span> n,<span style="color: #0000ff;">int</span> c[][max_size],<span style="color: #0000ff;">int</span><span style="color: #000000;"> ret[][max_size])</span><span style="color: #008080;">11</span> <span style="color: #000000;">{</span><span style="color: #008080;">12</span>     <span style="color: #0000ff;">int</span><span style="color: #000000;"> i,j,k;</span><span style="color: #008080;">13</span>     <span style="color: #0000ff;">int</span><span style="color: #000000;"> temp;</span><span style="color: #008080;">14</span>     <span style="color: #0000ff;">for</span>(j=<span style="color: #800080;">2</span>;j<=n;j++<span style="color: #000000;">)</span><span style="color: #008080;">15</span>         <span style="color: #0000ff;">for</span>(i=<span style="color: #800080;">1</span>;i<j;i++<span style="color: #000000;">)</span><span style="color: #008080;">16</span> <span style="color: #000000;">        {</span><span style="color: #008080;">17</span>             <span style="color: #0000ff;">for</span>(k=i+<span style="color: #800080;">1</span>;k<j;k++<span style="color: #000000;">)</span><span style="color: #008080;">18</span> <span style="color: #000000;">            {</span><span style="color: #008080;">19</span>                 <span style="color: #0000ff;">if</span>(s[k]>=f[i]&&f[k]<=<span style="color: #000000;">s[j])</span><span style="color: #008080;">20</span> <span style="color: #000000;">                {</span><span style="color: #008080;">21</span>                     temp=c[i][k]+c[k][j]+<span style="color: #800080;">1</span><span style="color: #000000;">;</span><span style="color: #008080;">22</span>                     <span style="color: #0000ff;">if</span>(c[i][j]<<span style="color: #000000;">temp)</span><span style="color: #008080;">23</span> <span style="color: #000000;">                    {</span><span style="color: #008080;">24</span>                         c[i][j]=<span style="color: #000000;">temp;</span><span style="color: #008080;">25</span>                         ret[i][j]=<span style="color: #000000;">k;</span><span style="color: #008080;">26</span> <span style="color: #000000;">                    }</span><span style="color: #008080;">27</span> <span style="color: #000000;">                }</span><span style="color: #008080;">28</span> <span style="color: #000000;">            }</span><span style="color: #008080;">29</span> <span style="color: #000000;">        }</span><span style="color: #008080;">30</span> <span style="color: #000000;">}</span><span style="color: #008080;">31</span> <span style="color: #008080;">32</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()</span><span style="color: #008080;">33</span> <span style="color: #000000;">{</span><span style="color: #008080;">34</span>     <span style="color: #0000ff;">int</span><span style="color: #000000;"> n;</span><span style="color: #008080;">35</span>     printf(<span style="color: #800000;">"</span><span style="color: #800000;">输入活动个数 n: </span><span style="color: #800000;">"</span><span style="color: #000000;">);</span><span style="color: #008080;">36</span>     <span style="color: #0000ff;">while</span>(~scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">n))</span><span style="color: #008080;">37</span> <span style="color: #000000;">    {</span><span style="color: #008080;">38</span>         memset(c,<span style="color: #800080;">0</span>,<span style="color: #0000ff;">sizeof</span>(<span style="color: #800080;">0</span><span style="color: #000000;">));</span><span style="color: #008080;">39</span>         memset(ret,<span style="color: #800080;">0</span>,<span style="color: #0000ff;">sizeof</span><span style="color: #000000;">(ret));</span><span style="color: #008080;">40</span>         printf(<span style="color: #800000;">"</span><span style="color: #800000;">\n输入活动开始以及结束时间\n</span><span style="color: #800000;">"</span><span style="color: #000000;">);</span><span style="color: #008080;">41</span>         <span style="color: #0000ff;">int</span><span style="color: #000000;"> i,j;</span><span style="color: #008080;">42</span>         <span style="color: #0000ff;">for</span>(i=<span style="color: #800080;">1</span>;i<=n;i++<span style="color: #000000;">)</span><span style="color: #008080;">43</span> <span style="color: #000000;">        {</span><span style="color: #008080;">44</span>             scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d%d</span><span style="color: #800000;">"</span>,&s[i],&<span style="color: #000000;">f[i]);</span><span style="color: #008080;">45</span> <span style="color: #000000;">        }</span><span style="color: #008080;">46</span> <span style="color: #000000;">        DP_SELECTOF(s,f,n,c,ret);</span><span style="color: #008080;">47</span>         printf(<span style="color: #800000;">"</span><span style="color: #800000;">最大子集的个数=%d\n</span><span style="color: #800000;">"</span>,c[<span style="color: #800080;">1</span>][n]+<span style="color: #800080;">2</span><span style="color: #000000;">);</span><span style="color: #008080;">48</span>     <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;</span><span style="color: #008080;">49</span> }

コードを表示

<span style="color: #008080;"> 1</span> #include <bits/stdc++.h><span style="color: #008080;"> 2</span> <span style="color: #0000ff;">#define</span> max_size 10010<span style="color: #008080;"> 3</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> s[max_size];</span><span style="color: #008080;"> 4</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> f[max_size];</span><span style="color: #008080;"> 5</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> ret[max_size];</span><span style="color: #008080;"> 6</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> c[max_size][max_size];</span><span style="color: #008080;"> 7</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;</span><span style="color: #008080;"> 8</span> <span style="color: #008080;"> 9</span> <span style="color: #0000ff;">void</span> GREEDY_ACTIVITY_SELECTOR(<span style="color: #0000ff;">int</span> *s,<span style="color: #0000ff;">int</span> *f,<span style="color: #0000ff;">int</span> n,<span style="color: #0000ff;">int</span> *<span style="color: #000000;">ret)</span><span style="color: #008080;">10</span> <span style="color: #000000;">{</span><span style="color: #008080;">11</span>     <span style="color: #0000ff;">int</span><span style="color: #000000;"> k,m;</span><span style="color: #008080;">12</span>     *ret++=<span style="color: #800080;">1</span><span style="color: #000000;">;</span><span style="color: #008080;">13</span>     k=<span style="color: #800080;">1</span><span style="color: #000000;">;</span><span style="color: #008080;">14</span>     <span style="color: #0000ff;">for</span>(m=<span style="color: #800080;">2</span>;m<=n;m++<span style="color: #000000;">)</span><span style="color: #008080;">15</span>         <span style="color: #0000ff;">if</span>(s[m]>=<span style="color: #000000;">f[k])</span><span style="color: #008080;">16</span> <span style="color: #000000;">        {</span><span style="color: #008080;">17</span>             *ret++=<span style="color: #000000;">m;</span><span style="color: #008080;">18</span>             k=<span style="color: #000000;">m;</span><span style="color: #008080;">19</span> <span style="color: #000000;">        }</span><span style="color: #008080;">20</span> <span style="color: #000000;">}</span><span style="color: #008080;">21</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()</span><span style="color: #008080;">22</span> <span style="color: #000000;">{</span><span style="color: #008080;">23</span>     <span style="color: #0000ff;">int</span><span style="color: #000000;"> n;</span><span style="color: #008080;">24</span>     printf(<span style="color: #800000;">"</span><span style="color: #800000;">输入活动个数 n: </span><span style="color: #800000;">"</span><span style="color: #000000;">);</span><span style="color: #008080;">25</span>     <span style="color: #0000ff;">while</span>(~scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">n))</span><span style="color: #008080;">26</span> <span style="color: #000000;">    {</span><span style="color: #008080;">27</span>         memset(s,<span style="color: #800080;">0</span>,<span style="color: #0000ff;">sizeof</span><span style="color: #000000;">(s));</span><span style="color: #008080;">28</span>         memset(f,<span style="color: #800080;">0</span>,<span style="color: #0000ff;">sizeof</span><span style="color: #000000;">(f));</span><span style="color: #008080;">29</span>         memset(c,<span style="color: #800080;">0</span>,<span style="color: #0000ff;">sizeof</span>(<span style="color: #800080;">0</span><span style="color: #000000;">));</span><span style="color: #008080;">30</span>         memset(ret,<span style="color: #800080;">0</span>,<span style="color: #0000ff;">sizeof</span><span style="color: #000000;">(ret));</span><span style="color: #008080;">31</span>         printf(<span style="color: #800000;">"</span><span style="color: #800000;">\n输入活动开始以及结束时间\n</span><span style="color: #800000;">"</span><span style="color: #000000;">);</span><span style="color: #008080;">32</span>         <span style="color: #0000ff;">int</span><span style="color: #000000;"> i,j;</span><span style="color: #008080;">33</span>         <span style="color: #0000ff;">for</span>(i=<span style="color: #800080;">1</span>;i<=n;i++<span style="color: #000000;">)</span><span style="color: #008080;">34</span> <span style="color: #000000;">        {</span><span style="color: #008080;">35</span>             scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d%d</span><span style="color: #800000;">"</span>,&s[i],&<span style="color: #000000;">f[i]);</span><span style="color: #008080;">36</span> <span style="color: #000000;">        }</span><span style="color: #008080;">37</span> <span style="color: #000000;">        GREEDY_ACTIVITY_SELECTOR(s,f,n,ret);</span><span style="color: #008080;">38</span>         <span style="color: #0000ff;">for</span>(i=<span style="color: #800080;">0</span>;i<=n;i++<span style="color: #000000;">)</span><span style="color: #008080;">39</span> <span style="color: #000000;">        {</span><span style="color: #008080;">40</span>             <span style="color: #0000ff;">if</span>(ret[i]!=<span style="color: #800080;">0</span><span style="color: #000000;">)</span><span style="color: #008080;">41</span>                 printf(<span style="color: #800000;">"</span><span style="color: #800000;">a%d </span><span style="color: #800000;">"</span><span style="color: #000000;">,ret[i]);</span><span style="color: #008080;">42</span> <span style="color: #000000;">        }</span><span style="color: #008080;">43</span>         printf(<span style="color: #800000;">"</span><span style="color: #800000;">\n</span><span style="color: #800000;">"</span><span style="color: #000000;">);</span><span style="color: #008080;">44</span> <span style="color: #000000;">    }</span><span style="color: #008080;">45</span> }