活动选择有关问题-PHP-Tutorial-php.cn

Heim

Backend-Entwicklung

PHP-Tutorial

活动选择有关问题

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 13, 2016 pm 12:27 PM

int max size

活动选择问题

问题描述：

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

。

从图中可以看出S中共有11个活动，最大的相互兼容的活动子集为:{a₁，a₄，a₈，a11，}和{a₂，a₄，a₉，a₁₁}。

2、动态规划解决过程

（1）活动选择问题的最优子结构

定义子问题解空间S_ij是S的子集，其中的每个获得都是互相兼容的。即每个活动都是在a_i结束之后开始，且在a_j开始之前结束。

为了方便讨论和后面的计算，添加两个虚构活动a₀和a_n+1，其中f₀=0，s_n+1=∞。

结论：当i≥j时，S_ij为空集。

如果活动按照结束时间单调递增排序，子问题空间被用来从S_ij中选择最大兼容活动子集，其中0≤i＜j≤n+1，所以其他的S_ij都是空集。

最优子结构为：假设S_ij的最优解A_ij包含活动a_k，则对S_ik的解A_ik和S_kj的解A_kj必定是最优的。

通过一个活动a_k将问题分成两个子问题，下面的公式可以计算出S_ij的解A_ij。

（2）一个递归解

　　设c[i][j]为S_ij中最大兼容子集中的活动数目，当S_ij为空集时，c[i][j]=0；当S_ij非空时，若a_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，则S_ij非空（此时满足f_i≤s_k且f_k≤s_j），找不到这样的a_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>

Nach dem Login kopieren

View Code

下面是贪心法的代码：

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

Nach dem Login kopieren

View Code

Erklärung dieser Website

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

KI-Kleiderentferner

Video Face Swap

Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heißer Artikel

Assassin's Creed Shadows: Seashell Riddle -Lösung

3 Wochen vor By DDD

Was ist neu in Windows 11 KB5054979 und wie Sie Update -Probleme beheben

2 Wochen vor By DDD

Wo kann man die Kransteuerungsschlüsselkarten in Atomfall finden

3 Wochen vor By DDD

<🎜>: Dead Rails - wie man jede Herausforderung abschließt

4 Wochen vor By DDD

Atomfall Guide: Gegenstandsstandorte, Questführer und Tipps

1 Monate vor By DDD

Heiße Werkzeuge

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

Wo ist der Login-Zugang für Gmail-E-Mail?

7681

Java-Tutorial

1639

CakePHP-Tutorial

1393

Laravel-Tutorial

1286

PHP-Tutorial

1229

Related knowledge

Verwenden Sie die Funktion File.length() von Java, um die Größe der Datei zu ermitteln Jul 24, 2023 am 08:36 AM

Verwenden Sie die File.length()-Funktion von Java, um die Größe einer Datei zu ermitteln. Die Dateigröße ist eine sehr häufige Anforderung beim Umgang mit Dateioperationen. Java bietet eine sehr praktische Möglichkeit, die Größe einer Datei zu ermitteln, d. h. mithilfe der Länge(. )-Methode der File-Klasse. In diesem Artikel wird erläutert, wie Sie mit dieser Methode die Größe einer Datei ermitteln und entsprechende Codebeispiele angeben. Zuerst müssen wir ein File-Objekt erstellen, um die Datei darzustellen, deren Größe wir ermitteln möchten. So erstellen Sie ein File-Objekt: Filef

iPhone 15 Pro Max vs. iPhone 14 Pro Max: Was sind die Vergleiche und Unterschiede zwischen ihnen? Sep 19, 2023 pm 08:29 PM

iPhone 15 Pro vs. iPhone 14 Pro: Vergleich der technischen Daten Hier ist ein Vergleich der technischen Daten zwischen iPhone 15 Pro Max und iPhone 14 Pro Max: iPhone 15 Pro Max iPhone 14 Pro Max Displaygröße 6,7 Zoll 6,7 Zoll Displaytechnologie Super Retina 2.000 Nits Abmessungen 6,29 x 3,5 Zoll 0,02 x 0,32 Zoll 6,33 x 3,06 x 0,31 Zoll Gewicht 221 Gramm 240 Gramm

Detaillierte Erläuterung der Methode zum Konvertieren des Int-Typs in Bytes in PHP Mar 06, 2024 pm 06:18 PM

Ausführliche Erläuterung der Methode zum Konvertieren des Int-Typs in Byte in PHP. In PHP müssen wir häufig den Integer-Typ (int) in den Byte-Typ (Byte) konvertieren, beispielsweise wenn es um Netzwerkdatenübertragung, Dateiverarbeitung oder Verschlüsselungsalgorithmen geht . In diesem Artikel wird detailliert beschrieben, wie der Typ int in den Typ byte konvertiert wird, und es werden spezifische Codebeispiele bereitgestellt. 1. Die Beziehung zwischen int-Typ und Byte Im Computerbereich stellt der grundlegende Datentyp int eine Ganzzahl dar, während Byte (Byte) eine Computerspeichereinheit ist, normalerweise 8-Bit-Binärdaten

C++-Programm zum Konvertieren von Variablen vom Typ Double in den Typ int Aug 25, 2023 pm 08:25 PM

In C++ können Variablen vom Typ int nur positive oder negative Ganzzahlwerte enthalten; sie können keine Dezimalwerte enthalten. Hierfür stehen Float- und Double-Werte zur Verfügung. Der Datentyp double wurde erstellt, um Dezimalzahlen mit bis zu sieben Nachkommastellen zu speichern. Die Konvertierung einer Ganzzahl in einen Double-Datentyp kann automatisch vom Compiler durchgeführt werden (sogenannte „implizite“ Konvertierung) oder sie kann vom Programmierer explizit vom Compiler angefordert werden (sogenannte „explizite“ Konvertierung). In den folgenden Abschnitten werden wir verschiedene Konvertierungsmethoden behandeln. Implizite Konvertierungen Der Compiler führt implizite Typkonvertierungen automatisch durch. Um dies zu erreichen, sind zwei Variablen erforderlich – eine vom Typ Gleitkomma und die andere vom Typ Ganzzahl. Wenn wir einer Ganzzahlvariablen einfach einen Gleitkommawert oder eine Variable zuweisen, kümmert sich der Compiler um alle anderen Dinge

So verwenden Sie HEIF Max (48 MP) und optimieren den Speicher auf dem iPhone 14 Pro Sep 21, 2023 pm 02:13 PM

Die neueste iPhone Pro-Serie ist mit einem leistungsstarken 48-MP-Sensor ausgestattet, der äußerst detaillierte und kristallklare Fotos gewährleistet, um jeden kostbaren Moment festzuhalten. Ein potenzieller Nachteil ist jedoch die Größe von Bildern in voller Auflösung, insbesondere von Bildern im ProRAW-Format. Obwohl der maximale Speicherplatz, den das iPhone bietet, 512 GB beträgt, kann die Aufnahme vieler ProRAW-Bilder (jeweils etwa 75 MP) und Videos (440 MB pro Minute, 60 FPS) schnell Ihren Speicherplatz beanspruchen. Dies kann zu Problemen führen, wenn Sie Ihr iPhone als Hauptkamera für große Projekte oder Reisen verwenden möchten. Aber wäre es nicht großartig, wenn Sie hochauflösende 48-Megapixel-Fotos aufnehmen könnten, ohne sich über Speicherbeschränkungen Gedanken machen zu müssen? es geht schnell

Was ist der Wertebereich von int32? Aug 11, 2023 pm 02:53 PM

Der Wertebereich von int32 reicht von -2 bis 31. Potenz bis 2 bis 31. Potenz minus 1, also -2147483648 bis 2147483647. int32 ist ein vorzeichenbehafteter Ganzzahltyp, was bedeutet, dass er positive Zahlen, negative Zahlen und Nullen darstellen kann. Er verwendet 1 Bit zur Darstellung des Vorzeichenbits und die restlichen 31 Bits werden zur Darstellung des numerischen Werts verwendet. Da ein Bit zur Darstellung des Vorzeichenbits verwendet wird, beträgt die effektive Anzahl der int32-Bits 31.

Vergleich der Akkulaufzeiten aller iPhone 15-Serien: iPhone 15 Plus schlägt 15 Pro Max Sep 30, 2023 pm 11:09 PM

Obwohl Apple die Videowiedergabezeit des iPhones einführen wird, um Benutzer darüber zu informieren, dass der iPhone-Akku fast leer ist. Aber normale Nutzer nutzen ihr iPhone nicht den ganzen Tag zum Anschauen von Videos. 7 iPhones im Alltagseinsatz auf Ausdauer getestet. Enthält 7 Modelle, darunter iPhone15ProMax, iPhone15Pro, iPhone15Plus, iPhone15, iPhone14ProMax, iPhone14 und iPhone13ProMax. Wenn wir einige alltägliche Anwendungen wie Spotify, Zoom, Tiktok, Headspace durchgehen und an Apps, Spiele usw. denken, können wir die Akkulaufzeit verschiedener iPhones sehen. Das

So erhalten Sie den maximalen Wert aus dem Stream in Java8 May 14, 2023 pm 03:43 PM

Der Stream von Java8 benötigt 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);}Hinweis: Die Größe wird hier durch positive und negative Zahlen und 0-Werte bestimmt. Anstatt es direkt zu schreiben if(a>b){returna;}elseretur

See all articles