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

Maison

développement back-end

tutoriel php

活动选择有关问题

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>

Copier après la connexion

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>

Copier après la connexion

View Code

Déclaration de ce site Web

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

Générez AI Hentai gratuitement.

Afficher plus

Article chaud

Assassin's Creed Shadows: Solution d'énigmes de coquille

3 Il y a quelques semaines By DDD

Quoi de neuf dans Windows 11 KB5054979 et comment résoudre les problèmes de mise à jour

2 Il y a quelques semaines By DDD

Où trouver la courte de la grue à atomide atomique

3 Il y a quelques semaines By DDD

Économie dans R.E.P.O. Expliqué (et enregistrer des fichiers)

1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌

Assassin's Creed Shadows - Comment trouver le forgeron et déverrouiller les armes et la personnalisation des armes

4 Il y a quelques semaines By DDD

Afficher plus

Outils chauds

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Afficher plus

Sujets chauds

Où se trouve l'entrée de connexion pour la messagerie Gmail ?

7569

Tutoriel CakePHP

1386

Quel est le format du nom de compte de Steam

Clé d&amp;amp;amp;amp;amp;amp;#39;activation Win11 permanent

NYT Connexions Indices et réponses

107

Afficher plus

Related knowledge

Utilisez la fonction File.length() de Java pour obtenir la taille du fichier Jul 24, 2023 am 08:36 AM

Utilisez la fonction File.length() de Java pour obtenir la taille d'un fichier. La taille du fichier est une exigence très courante lors des opérations sur les fichiers. Java fournit un moyen très pratique d'obtenir la taille d'un fichier, c'est-à-dire en utilisant la longueur (. ) méthode de la classe File . Cet article explique comment utiliser cette méthode pour obtenir la taille d'un fichier et donne des exemples de code correspondants. Tout d’abord, nous devons créer un objet File pour représenter le fichier dont nous voulons obtenir la taille. Voici comment créer un objet File : Filef

iPhone 15 Pro Max vs iPhone 14 Pro Max : quelles sont les comparaisons et les différences entre eux ? Sep 19, 2023 pm 08:29 PM

iPhone 15 Pro contre iPhone 14 Pro : comparaison des spécifications Voici une comparaison des spécifications entre l'iPhone 15 Pro Max et l'iPhone 14 Pro Max : iPhone 15 Pro Max iPhone 14 Pro Max Taille de l'écran 6,7 pouces 6,7 pouces Technologie d'affichage Super Retina 2 000 nits Dimensions 6,29x3 0,02x0,32 pouces 6,33x3,06x0,31 pouces Poids 221 grammes 240 grammes

Explication détaillée de la méthode de conversion du type int en octets en PHP Mar 06, 2024 pm 06:18 PM

Explication détaillée de la méthode de conversion du type int en octet en PHP En PHP, nous avons souvent besoin de convertir le type entier (int) en type octet (Byte), par exemple lorsqu'il s'agit de transmission de données réseau, de traitement de fichiers ou d'algorithmes de cryptage . Cet article présentera en détail comment convertir le type int en type byte et fournira des exemples de code spécifiques. 1. La relation entre le type int et l'octet Dans le domaine informatique, le type de données de base int représente un entier, tandis que l'octet (Byte) est une unité de stockage informatique, généralement des données binaires de 8 bits.

Programme C++ pour convertir une variable de type double en type int Aug 25, 2023 pm 08:25 PM

En C++, les variables de type int ne peuvent contenir que des valeurs entières positives ou négatives ; elles ne peuvent pas contenir de valeurs décimales. Des valeurs float et double sont disponibles à cet effet. Le type de données double a été créé pour stocker des décimales jusqu'à sept chiffres après la virgule. La conversion d'un entier en type de données double peut être effectuée automatiquement par le compilateur (appelée conversion "implicite"), ou elle peut être explicitement demandée par le programmeur au compilateur (appelée conversion "explicite"). Dans les sections suivantes, nous aborderons différentes méthodes de conversion. Conversions implicites Le compilateur effectue automatiquement des conversions de type implicites. Pour y parvenir, deux variables sont nécessaires : l’une de type virgule flottante et l’autre de type entier. Lorsque nous attribuons simplement une valeur ou une variable à virgule flottante à une variable entière, le compilateur s'occupe de toutes les autres choses.

Comment utiliser HEIF Max (48 MP) et optimiser le stockage sur iPhone 14 Pro Sep 21, 2023 pm 02:13 PM

La dernière série d'iPhone Pro est équipée d'un puissant capteur de 48 MP qui garantit des photos très détaillées et d'une clarté cristalline pour capturer chaque instant précieux. Cependant, un inconvénient potentiel est la taille des images en pleine résolution, notamment celles au format ProRAW. Bien que l'espace de stockage maximum offert par l'iPhone soit de 512 Go, la capture de nombreuses images ProRAW (environ 75 MP chacune) et de vidéos (440 Mo par minute, 60 FPS) peut rapidement consommer votre espace de stockage. Cela peut poser des problèmes si vous envisagez d'utiliser votre iPhone comme appareil photo principal pour de grands projets ou des voyages. Mais ne serait-il pas formidable si vous pouviez prendre ces photos haute résolution de 48 MP sans vous soucier des limitations de stockage ? c'est rapide

Comparaison de la durée de vie de la batterie de toutes les séries d'iPhone 15 : l'iPhone 15 Plus bat le 15 Pro Max Sep 30, 2023 pm 11:09 PM

Bien qu'Apple lancera le temps de lecture vidéo de l'iPhone pour informer les utilisateurs que la batterie de l'iPhone est presque disponible. Mais les utilisateurs normaux n’utilisent pas leur iPhone pour visionner des vidéos à longueur de journée. 7 iPhones testés pour leur endurance dans les applications quotidiennes. Comprend 7 modèles dont iPhone15ProMax, iPhone15Pro, iPhone15Plus, iPhone15, iPhone14ProMax, iPhone14 et iPhone13ProMax. En parcourant certaines applications quotidiennes, telles que Spotify, Zoom, Tiktok, Headspace, pensez aux applications, aux jeux, etc., nous pouvons voir la durée de vie de la batterie des différents iPhones. ce

Quelle est la plage de valeurs de int32 ? Aug 11, 2023 pm 02:53 PM

La plage de valeurs de int32 va de -2 à la puissance 31 à 2 à la puissance 31 moins 1, soit -2147483648 à 2147483647. int32 est un type entier signé, ce qui signifie qu'il peut représenter des nombres positifs, des nombres négatifs et zéro. Il utilise 1 bit pour représenter le bit de signe et les 31 bits restants sont utilisés pour représenter la valeur numérique. Puisqu’un bit est utilisé pour représenter le bit de signe, le nombre effectif de bits int32 est 31.

Comment obtenir la valeur maximale du flux dans Java8 May 14, 2023 pm 03:43 PM

Le flux de java8 prend 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);}Remarque : la taille est déterminée ici par des nombres positifs et négatifs et des valeurs 0. Au lieu de l'écrire directement if(a>b){returna;}elseretur

See all articles