アクティビティの選択に関する質問-PHPチュートリアル-php.cn

ホームページ

バックエンド開発

PHPチュートリアル

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 13, 2016 pm 12:27 PM

intmaxsize

アクティビティ選択問題

問題の説明:

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

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

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

個人テストコード:

コードを表示

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

<span style="color: #008080;"> 1</span> #include <bits><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)<span style="color: #008080;">15</span>         <span style="color: #0000ff;">for</span>(i=<span style="color: #800080;">1</span>;i<j style="color: #000000;">)<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 style="color: #000000;">)<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]s[j])<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]temp)<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)<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> }</j></j></bits>

コードを表示

<span style="color: #008080;"> 1</span> #include <bits><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)<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)<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)<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> }</bits>

声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

セッションを保存するためにデータベースを使用することの利点は何ですか？Apr 24, 2025 am 12:16 AM

データベースストレージセッションを使用することの主な利点には、持続性、スケーラビリティ、セキュリティが含まれます。 1。永続性：サーバーが再起動しても、セッションデータは変更されないままになります。 2。スケーラビリティ：分散システムに適用され、セッションデータが複数のサーバー間で同期されるようにします。 3。セキュリティ：データベースは、機密情報を保護するための暗号化されたストレージを提供します。

PHPでカスタムセッション処理をどのように実装しますか？Apr 24, 2025 am 12:16 AM

PHPでのカスタムセッション処理の実装は、SessionHandlerInterfaceインターフェイスを実装することで実行できます。具体的な手順には、次のものが含まれます。1）CussentsessionHandlerなどのSessionHandlerInterfaceを実装するクラスの作成。 2）セッションデータのライフサイクルとストレージ方法を定義するためのインターフェイス（オープン、クローズ、読み取り、書き込み、破壊、GCなど）の書き換え方法。 3）PHPスクリプトでカスタムセッションプロセッサを登録し、セッションを開始します。これにより、データをMySQLやRedisなどのメディアに保存して、パフォーマンス、セキュリティ、スケーラビリティを改善できます。

セッションIDとは何ですか？Apr 24, 2025 am 12:13 AM

SessionIDは、ユーザーセッションのステータスを追跡するためにWebアプリケーションで使用されるメカニズムです。 1.ユーザーとサーバー間の複数のインタラクション中にユーザーのID情報を維持するために使用されるランダムに生成された文字列です。 2。サーバーは、ユーザーの複数のリクエストでこれらの要求を識別および関連付けるのに役立つCookieまたはURLパラメーターを介してクライアントに生成および送信します。 3.生成は通常、ランダムアルゴリズムを使用して、一意性と予測不可能性を確保します。 4.実際の開発では、Redisなどのメモリ内データベースを使用してセッションデータを保存してパフォーマンスとセキュリティを改善できます。

ステートレス環境（APIなど）でセッションをどのように処理しますか？Apr 24, 2025 am 12:12 AM

APIなどのステートレス環境でのセッションの管理は、JWTまたはCookieを使用して達成できます。 1。JWTは、無国籍とスケーラビリティに適していますが、ビッグデータに関してはサイズが大きいです。 2.cookiesはより伝統的で実装が簡単ですが、セキュリティを確保するために慎重に構成する必要があります。

セッションに関連するクロスサイトスクリプティング（XSS）攻撃からどのように保護できますか？

セッション関連のXSS攻撃からアプリケーションを保護するには、次の測定が必要です。1。セッションCookieを保護するためにHTTPonlyとセキュアフラグを設定します。 2。すべてのユーザー入力のエクスポートコード。 3.コンテンツセキュリティポリシー（CSP）を実装して、スクリプトソースを制限します。これらのポリシーを通じて、セッション関連のXSS攻撃を効果的に保護し、ユーザーデータを確保できます。

PHPセッションのパフォーマンスを最適化するにはどうすればよいですか？Apr 23, 2025 am 12:13 AM

PHPセッションのパフォーマンスを最適化する方法は次のとおりです。1。遅延セッション開始、2。データベースを使用してセッションを保存します。これらの戦略は、高い並行性環境でのアプリケーションの効率を大幅に改善できます。

session.gc_maxlifetime構成設定とは何ですか？Apr 23, 2025 am 12:10 AM

thesession.gc_maxlifettinginttinginphpdethinesthelifsessessiondata、setinseconds.1）it'sconfiguredinphp.iniorviaini_set（）。 2）AbalanceSneededToAvoidPerformanceIssues andunexpectedLogouts.3）php'sgarbagecollectionisisprobabilistic、影響を受けたBygc_probabi

PHPでセッション名をどのように構成しますか？Apr 23, 2025 am 12:08 AM

PHPでは、session_name（）関数を使用してセッション名を構成できます。特定の手順は次のとおりです。1。session_name（）関数を使用して、session_name（ "my_session"）などのセッション名を設定します。 2。セッション名を設定した後、session_start（）を呼び出してセッションを開始します。セッション名の構成は、複数のアプリケーション間のセッションデータの競合を回避し、セキュリティを強化することができますが、セッション名の一意性、セキュリティ、長さ、設定タイミングに注意してください。

See all articles

ホットAIツール

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

脱衣画像を無料で

Clothoff.io

AI衣類リムーバー

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ビジュアル Web 開発ツール

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コードプロンプト機能はサポートされていません

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポートライブラリとヘッダーファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。