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

ホームページ

バックエンド開発

PHPチュートリアル

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 13, 2016 pm 12:27 PM

int max size

アクティビティ選択問題

問題の説明:

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/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> }

ログイン後にコピー

このウェブサイトの声明

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

ホットAIツール

ホットツール

ホットトピック

Gmailメールのログイン入り口はどこですか？

7548

CakePHP チュートリアル

1382

Steamのアカウント名の形式は何ですか

Win11 Activation Key Permanent

NYTの接続はヒントと回答です

Related knowledge

JavaのFile.length()関数を使用してファイルのサイズを取得します。 Jul 24, 2023 am 08:36 AM

ファイルのサイズを取得するには、Java の File.length() 関数を使用します。ファイル操作を扱うとき、ファイルサイズは非常に一般的な要件です。Java では、ファイルのサイズを取得するための非常に便利な方法、つまり length( ) File クラスのメソッド。この記事では、このメソッドを使用してファイルのサイズを取得する方法と、対応するコード例を紹介します。まず、サイズを取得したいファイルを表す File オブジェクトを作成する必要があります。 File オブジェクトを作成する方法は次のとおりです: Filef

iPhone 15 Pro Max と iPhone 14 Pro Max: 両者の比較と違いは何ですか? Sep 19, 2023 pm 08:29 PM

iPhone 15 Pro と iPhone 14 Pro: スペックの比較 iPhone 15 Pro Max と iPhone 14 Pro Max のスペック比較は次のとおりです: iPhone 15 Pro Max iPhone 14 Pro Max ディスプレイサイズ 6.7 インチ 6.7 インチディスプレイテクノロジー Super Retina 2,000 nit 寸法 6.29x3 0.02x0.32 インチ 6.33x3.06x0.31 インチ重量 221 グラム 240 グラム

PHPでint型をbytesに変換する方法を詳しく解説 Mar 06, 2024 pm 06:18 PM

PHPでint型をbyte型に変換する方法を詳しく解説 PHPでは、ネットワークデータ送信やファイル処理、暗号化アルゴリズムなどを扱う場合など、整数型(int)をバイト型(Byte)に変換する必要が生じることがよくあります。。この記事では、int型をbyte型に変換する方法と具体的なコード例を詳しく紹介します。 1. int 型と byte の関係コンピュータ分野では、基本データ型 int は整数を表しますが、byte (バイト) はコンピュータの記憶単位で、通常は 8 ビットのバイナリデータです

double型変数をint型に変換するC++プログラム Aug 25, 2023 pm 08:25 PM

C++ では、int 型の変数は正または負の整数値のみを保持でき、10 進数値を保持できません。この目的に使用できる float 値と double 値があります。 double データ型は、小数点以下 7 桁までの小数を格納するために作成されました。整数から double データ型への変換は、コンパイラによって自動的に実行することも (「暗黙的」変換と呼ばれます)、プログラマがコンパイラに明示的に要求することもできます (「明示的」変換と呼ばれます)。次のセクションでは、さまざまな変換方法について説明します。暗黙的な変換コンパイラは暗黙的な型変換を自動的に実行します。これを実現するには、浮動小数点型と整数型の 2 つの変数が必要です。浮動小数点値または変数を整数変数に代入するだけでは、コンパイラが他のすべてのことを処理します。

HEIF Max (48 MP) を使用して iPhone 14 Pro のストレージを最適化する方法 Sep 21, 2023 pm 02:13 PM

最新の iPhone Pro シリーズには、強力な 48MP センサーが搭載されており、非常に詳細で非常に鮮明な写真を保証し、あらゆる貴重な瞬間を捉えます。ただし、潜在的な欠点の 1 つは、フル解像度の画像、特に ProRAW 形式の画像のサイズです。 iPhone が提供する最大ストレージ容量は 512GB ですが、ProRAW 画像 (それぞれ約 75MP) やビデオ (1 分あたり 440MB、60FPS) を大量にキャプチャすると、ストレージ容量がすぐに消費されてしまいます。大規模なプロジェクトや旅行で iPhone をメインカメラとして使用する予定がある場合、これにより問題が発生する可能性があります。しかし、ストレージの制限を気にせずに、高解像度の 48MP 写真を撮影できたら素晴らしいと思いませんか?早いです

すべての iPhone 15 シリーズのバッテリー寿命の比較: iPhone 15 Plus が 15 Pro Max を上回る Sep 30, 2023 pm 11:09 PM

ただし、Apple は iPhone のバッテリーが残りわずかであることをユーザーに知らせるために、iPhone のビデオ再生時間を発表します。しかし、一般のユーザーは、iPhone を 1 日中ビデオを見るために使用するわけではありません。 7 台の iPhone が日常的な用途で耐久性をテストされました。 iPhone15ProMax、iPhone15Pro、iPhone15Plus、iPhone15、iPhone14ProMax、iPhone14、iPhone13ProMaxの7機種が含まれます。 Spotify、Zoom、Tiktok、Headspace、アプリ、ゲームなどの日常的なアプリケーションを実行すると、さまざまな iPhone のバッテリー寿命がわかります。これ

int32の値の範囲はどれくらいですか？ Aug 11, 2023 pm 02:53 PM

int32 の値の範囲は、-2 の 31 乗から 2 の 31 乗 - 1、つまり -2147483648 ～ 2147483647 です。 int32 は符号付き整数型です。つまり、正の数、負の数、ゼロを表現できます。1 ビットを符号ビットの表現に使用し、残りの 31 ビットは数値の表現に使用されます。符号ビットを表すために 1 ビットが使用されるため、int32 の有効ビット数は 31 です。

Java8でストリームから最大値を取得する方法 May 14, 2023 pm 03:43 PM

java8 のストリームは maxpublicstaticvoidmain(String[]args){Listlist=Arrays.asList(1,2,3,4,5,6);Integermax=list.stream().max((a,b)->{if ( a>b){return1;}elsereturn-1;}).get();System.out.println(max);}注: ここでは、サイズは正と負の数値および 0 の値によって決定されます。直接書く代わりに if(a>b){returna;}elseretur

See all articles

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

ホットAIツール

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

AI Hentai Generator

人気の記事

ホットツール

メモ帳++7.3.1

SublimeText3 中国語版

ゼンドスタジオ 13.0.1

ドリームウィーバー CS6

SublimeText3 Mac版

ホットトピック