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

Home

Backend Development

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>

Copy after login

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>

Copy after login

View Code

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress images for free

Clothoff.io

AI clothes remover

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Assassin's Creed Shadows: Seashell Riddle Solution

3 weeks ago By DDD

What's New in Windows 11 KB5054979 & How to Fix Update Issues

2 weeks ago By DDD

Where to find the Crane Control Keycard in Atomfall

3 weeks ago By DDD

Assassin's Creed Shadows - How To Find The Blacksmith And Unlock Weapon And Armour Customisation

1 months ago By DDD

Roblox: Dead Rails - How To Complete Every Challenge

3 weeks ago By DDD

Hot Tools

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Where is the login entrance for gmail email?

7596

CakePHP Tutorial

1386

What is the format of the account name of steam

win11 activation key permanent

nyt connections hints and answers

123

Related knowledge

Use java's File.length() function to get the size of the file Jul 24, 2023 am 08:36 AM

Use Java's File.length() function to get the size of a file. File size is a very common requirement when dealing with file operations. Java provides a very convenient way to get the size of a file, that is, using the length() method of the File class. . This article will introduce how to use this method to get the size of a file and give corresponding code examples. First, we need to create a File object to represent the file we want to get the size of. Here is how to create a File object: Filef

iPhone 15 Pro Max vs iPhone 14 Pro Max: What are the comparisons and differences between them? Sep 19, 2023 pm 08:29 PM

iPhone 15 Pro vs. iPhone 14 Pro: Specs Comparison Here is a spec comparison between iPhone 15 Pro Max and iPhone 14 Pro Max: iPhone 15 Pro Max iPhone 14 Pro Max Display size 6.7 inches 6.7 inches Display technology Super Retina 2,000 nits Dimensions 6.29x3.02x0.32 inches 6.33x3.06x0.31 inches Weight 221 grams 240 grams

Detailed explanation of the method of converting int type to bytes in PHP Mar 06, 2024 pm 06:18 PM

Detailed explanation of the method of converting int type to byte in PHP In PHP, we often need to convert the integer type (int) to the byte (Byte) type, such as when dealing with network data transmission, file processing, or encryption algorithms. This article will introduce in detail how to convert the int type to the byte type and provide specific code examples. 1. The relationship between int type and byte In the computer field, the basic data type int represents an integer, while byte (Byte) is a computer storage unit, usually 8-bit binary data

C++ program to convert double type variable to int type Aug 25, 2023 pm 08:25 PM

In C++, variables of type int can only hold positive or negative integer values; they cannot hold decimal values. There are float and double values available for this purpose. The double data type was created to store decimals up to seven digits after the decimal point. Conversion of an integer to a double data type can be done automatically by the compiler (called an "implicit" conversion), or it can be explicitly requested by the programmer from the compiler (called an "explicit" conversion). In the following sections, we'll cover various conversion methods. Implicit conversions The compiler performs implicit type conversions automatically. To achieve this, two variables are required - one of floating point type and the other of integer type. When we simply assign a floating point value or variable to an integer variable, the compiler takes care of all the other things

How to use HEIF Max (48 MP) and optimize storage on iPhone 14 Pro Sep 21, 2023 pm 02:13 PM

The latest iPhone Pro series is equipped with a powerful 48MP sensor that ensures highly detailed and crystal clear photos to capture every precious moment. However, one potential drawback is the size of full-resolution images, especially those in ProRAW format. Although the maximum storage space offered by the iPhone is 512GB, capturing a lot of ProRAW images (about 75MP each) and video (440MB per minute, 60FPS) can quickly eat up your storage space. This can cause problems if you plan to use your iPhone as your main camera for large projects or travel. But wouldn't it be great if you could take those high-resolution 48MP photos without worrying about storage limitations? it's quick

What is the value range of int32? Aug 11, 2023 pm 02:53 PM

The value range of int32 is from -2 to the 31st power to 2 to the 31st power minus 1, that is, -2147483648 to 2147483647. int32 is a signed integer type, which means it can represent positive numbers, negative numbers, and zero. It uses 1 bit to represent the sign bit, and the remaining 31 bits are used to represent the numerical value. Since one bit is used to represent the sign bit, the effective number of int32 bits is 31.

Battery life comparison of all iPhone 15 series: iPhone 15 Plus beats 15 Pro Max Sep 30, 2023 pm 11:09 PM

Although Apple will launch the iPhone's video playback time to let users know that the iPhone battery is almost available. But normal users don't use their iPhone to view videos all day long. 7 iPhones tested for endurance in daily applications. Includes 7 models including iPhone15ProMax, iPhone15Pro, iPhone15Plus, iPhone15, iPhone14ProMax, iPhone14 and iPhone13ProMax. Running through some daily applications, such as Spotify, Zoom, Tiktok, Headspace, think about Apps, games, etc., we can see the battery life of different iPhones. this

How to get max value from stream in java8 May 14, 2023 pm 03:43 PM

java8's stream takes 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);}Note: The size is determined here through positive and negative numbers and 0 values. Instead of writing it directly if(a>b){returna;}elseretur

See all articles