2014高教社杯全國大學生數學建模競賽D題目

題目描述

儲藥柜的結構類似于書櫥，通常由若干個橫向隔板和豎向隔板將儲藥柜分割成若干個儲藥槽(如圖1所示)。為保證藥品分揀的準確率，防止發藥錯誤，一個儲藥槽內只能擺放同一種藥品。藥品在儲藥槽中的排列方式如圖2所示。藥品從后端放入，從前端取出。一個實際儲藥柜中藥品的擺放情況如圖3所示。
為保證藥品在儲藥槽內順利出入，要求藥盒與兩側豎向隔板之間、與上下兩層橫向隔板之間應留2mm的間隙，同時還要求藥盒在儲藥槽內推送過程中不會出現并排重疊、側翻或水平旋轉。在忽略橫向和豎向隔板厚度的情況下，建立數學模型，給出下面幾個問題的解決方案。

1. 藥房內的盒裝藥品種類繁多，藥盒尺寸規格差異較大，附件1中給出了一些藥盒的規格。請利用附件1的數據，給出豎向隔板間距類型最少的儲藥柜設計方案，包括類型的數量和每種類型所對應的藥盒規格。
2. 藥盒與兩側豎向隔板之間的間隙超出2mm的部分可視為寬度冗余。增加豎向隔板的間距類型數量可以有效地減少寬度冗余，但會增加儲藥柜的加工成本，同時降低了儲藥槽的適應能力。設計時希望總寬度冗余盡可能小，同時也希望間距的類型數量盡可能少。仍利用附件1的數據，給出合理的豎向隔板間距類型的數量以及每種類型對應的藥品編號。
3. 考慮補藥的便利性，儲藥柜的寬度不超過2.5m、高度不超過2m，傳送裝置占用的高度為0.5m，即儲藥柜的最大允許有效高度為1.5m。藥盒與兩層橫向隔板之間的間隙超出2mm的部分可視為高度冗余，平面冗余＝高度冗余×寬度冗余。在問題2計算結果的基礎上，確定儲藥柜橫向隔板間距的類型數量，使得儲藥柜的總平面冗余量盡可能地小，且橫向隔板間距的類型數量也盡可能地少。
4. 附件2給出了每一種藥品編號對應的最大日需求量。在儲藥槽的長度為1.5m、每天僅集中補藥一次的情況下，請計算每一種藥品需要的儲藥槽個數。為保證藥房儲藥滿足需求，根據問題3中單個儲藥柜的規格，計算最少需要多少個儲藥柜。

提出關鍵點

一個儲藥槽內只能擺放同一種藥品。
要求藥盒與兩側豎向隔板之間、與上下兩層橫向隔板之間應留2mm的間隙，同時還要求藥盒在儲藥槽內推送過程中不會出現并排重疊、側翻或水平旋轉。在忽略橫向和豎向隔板厚度的情況下，建立數學模型。

建立數學模型

模型一：儲藥槽和藥盒關系模型

已知藥盒長寬高分別是$a,b,c$毫米,設計儲藥槽長寬高分別是$x,y,z$毫米。

要求藥盒在儲藥槽內推送過程中不會出現:

1.并排重疊 ，

即儲藥槽高度不能高于兩倍的藥盒高，儲藥槽寬度不能高于兩倍的藥盒寬
$\{\begin{array}{l}z<2c\\ y<2b\end{array}$

2.側翻，

如上圖，紅色為藥盒，分兩種情況，情況一:綠色為儲藥槽；情況二:黑色為儲藥槽。

假設考慮的是不能完全側翻情況，那么模型為:
{ z < b 2 + c 2 + M ( 1 ? μ ) y < b 2 + c 2 + M ( 1 ? v ) μ + v ≥ 1 μ , v ∈ { 0 , 1 } \begin{cases} z\lt \sqrt{b^2+c^2} + M(1-\mu)\\ y \lt \sqrt{b^2+c^2} + M(1-v)\\ \mu + v \ge 1\\ \mu,v \in \set{0,1} \end{cases} ? ? ??z<b2+c2 ?+M(1?μ)y<b2+c2 ?+M(1?v)μ+v≥1μ,v∈{0,1}?
其中 $M$為定值，并且$M\ge \sqrt{b^2+c^2}$

考慮實際情況，假設側翻角度超過$45$度即為側翻
觀察上圖，下方綠線和紅線夾角為45度時為極限角度可以得到：
$y=\frac{\sqrt{2}}{2}(a+b)$
并且側翻時側面解刨圖來看，長方形的一個點會和儲藥槽底部接觸，模擬物體旋轉過程發現當長方形的對角線和底部垂直時候，整個物體觸頂高度達到最高值。也就是說如果儲藥槽設計高度低于物體的對角線長度物體將無法側翻
可以得到模型:
{ z < b 2 + c 2 + M ( 1 ? μ ) y < 2 2 ( a + b ) + M ( 1 ? v ) μ + v ≥ 1 μ , v ∈ { 0 , 1 } \begin{cases} z\lt \sqrt{b^2+c^2} + M(1-\mu)\\ y \lt \dfrac{\sqrt{2}}{2}(a+b) + M(1-v)\\ \mu + v \ge 1\\ \mu,v \in \set{0,1} \end{cases} ? ? ??z<b2+c2 ?+M(1?μ)y<22 ??(a+b)+M(1?v)μ+v≥1μ,v∈{0,1}?
其中 $M$為定值，并且$M\ge \max (\sqrt{b^2+c^2},\frac{\sqrt{2}}{2}(a+b))$

將45度推廣為$\alpha$度(準確來講是物體抬起的角度)，模型將變為
{ z < b 2 + c 2 + M ( 1 ? μ ) y < b cos ? α + c cos ? ( π 2 ? α ) + M ( 1 ? v ) μ + v ≥ 1 μ , v ∈ { 0 , 1 } \begin{cases} z\lt \sqrt{b^2+c^2} + M(1-\mu)\\ y \lt b\cos{\alpha}+c\cos{(\dfrac{\pi}{2}-\alpha)} + M(1-v)\\ \mu + v \ge 1\\ \mu,v \in \set{0,1} \end{cases} ? ? ??z<b2+c2 ?+M(1?μ)y<bcosα+ccos(2π??α)+M(1?v)μ+v≥1μ,v∈{0,1}?
其中 $M$為定值，并且$M\ge \max (\sqrt{b^2+c^2},b\cos \alpha +c\cos (\frac{\pi }{2}?\alpha ))$

3.水平旋轉 ,

實際上和側翻的情況一類似，只是寬和高變成了長和寬
設物體水平旋轉了$\alpha$度就稱為水平旋轉了
$y<b\cos \alpha +a\cos (\frac{\pi }{2}?\alpha )$

要求藥盒與兩側豎向隔板之間、與上下兩層橫向隔板之間應留2mm的間隙

$\{\begin{array}{l}z\ge c+2\\ y\ge b+2\end{array}$

建立解決問題的數學模型

問題一

假設已知所有盒裝藥品所需的儲藥槽寬度$x$約束,和所有盒裝藥品總數$N$
即$a_i\le x_i<b_i,i=1,2,\mathrm{3...}N$

那么

解決模型一:

設$y_j$為第$j$種豎向隔板間距類型大小
$g_{ij}$表示第$i$種藥盒可不可以放進第$j$種藥槽里面

{ min ? ∑ j = 1 M f j a i g i j ≤ y j f j < b i + M ′ ( 1 ? g i j ) ∑ j = 1 M g i j ≥ 1 f j , g i j ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} \min \displaystyle\sum_{j=1}^M f_j\\ a_ig_{ij} \le y_jf_j \lt b_i+M'(1-g_{ij})\\ \displaystyle\sum_{j=1}^M g_{ij} \ge 1\\ f_j , g_{ij} \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} ? ? ??minj=1∑M?fj?ai?gij?≤yj?fj?<bi?+M′(1?gij?)j=1∑M?gij?≥1fj?,gij?∈{0,1}i=1,2,3,...N,j=1,2,3,...M?
$M^{\prime }\ge {\max }_{i=1}^N{b}_i$
這種模型就要先求出所有可能為豎向隔板間距類型的大小

解決模型二:

我們可以得出第$i$種藥盒能放進的藥槽都得出來,記做$d_{ij}$
如果$d_{ij}=1$表示得出第$i$種藥盒能放進第$j$種藥槽，反之不能
{ min ? ∑ j = 1 M f j ∑ j = 1 M d i j f j > 1 f j , g i j ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} \min \displaystyle\sum_{j=1}^M f_j\\ \displaystyle\sum_{j=1}^M d_{ij}f_j \gt 1\\ f_j , g_{ij} \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} ? ? ??minj=1∑M?fj?j=1∑M?dij?fj?>1fj?,gij?∈{0,1}i=1,2,3,...N,j=1,2,3,...M?

解決模型三:

{ a i g i ≤ x j < b i g i max ? ∑ i = 1 N g i f j , g i ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \max \displaystyle\sum_{i=1}^N g_i\\ f_j , g_i \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} ? ? ??ai?gi?≤xj?<bi?gi?maxi=1∑N?gi?fj?,gi?∈{0,1}i=1,2,3,...N,j=1,2,3,...M?
不斷增加$M$的值，直到答案$\sum _{i=1}^N{g}_i\ge N$,就求出其中一組解

問題二

簡單來說就是要求所有 藥盒與兩側豎向隔板之間的間隙超出2mm的部分 之和最小
利用上一問的模型三:
{ a i g i ≤ x j < b i g i max ? ∑ i = 1 N g i f j , g i ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \max \displaystyle\sum_{i=1}^N g_i\\ f_j , g_i \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} ? ? ??ai?gi?≤xj?<bi?gi?maxi=1∑N?gi?fj?,gi?∈{0,1}i=1,2,3,...N,j=1,2,3,...M?
其中$M$的臨界值$M_1$在問題一已經求出
所以就可以規定$M\ge M_1$

同問題一的假設:
假設已知所有盒裝藥品所需的儲藥槽寬度$x$約束,和所有盒裝藥品總數$N$
即$a_i\le x_i<b_i,i=1,2,\mathrm{3...}N$
觀察模型一：儲藥槽和藥盒關系模型中的所有約束條件，發現$a_i$只能是藥盒的寬度加兩毫米，為已知量
那么藥盒與兩側豎向隔板之間的間隙超出2mm的部分可以表示為:
$x_i?a_i$
因為還要約束兩側豎向隔板之間的間隙的種類,所以
$min\sum _{j=1}^M\sum _{i=1}^N{x}_j?a_i,x_j\ge a_i$
得到

模型一:

{ m i n ∑ j = 1 M ∑ i = 1 N x j ? a i , x j ≥ a i a i g i ≤ x j < b i g i ∑ i = 1 N g i = N f j , g i ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} min \displaystyle\sum_{j=1}^M\displaystyle\sum_{i=1}^N x_j-a_i , x_j\ge a_i\\ a_ig_i \le x_j \lt b_ig_i\\ \displaystyle\sum_{i=1}^N g_i = N\\ f_j , g_i \in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} ? ? ??minj=1∑M?i=1∑N?xj??ai?,xj?≥ai?ai?gi?≤xj?<bi?gi?i=1∑N?gi?=Nfj?,gi?∈{0,1}i=1,2,3,...N,j=1,2,3,...M?

當然這種模型求解/優化都不容易
如果換個思路，在問題一已知有多少種兩側豎向隔板之間的間隙的種類了，并且求出了對應藥盒對應的兩側豎向隔板之間的間隙，那么就可以把兩側豎向隔板之間的間隙相同的都分為一組，最后形成$M$組藥盒和對應的兩側豎向隔板之間的間隙

只需要每一組對應的兩側豎向隔板之間的間隙都取最小值，那么$M$組加起來也就是所有 藥盒與兩側豎向隔板之間的間隙超出2mm的部分 之和最小

那么

模型二:

{ a i g i ≤ x j < b i g i ∑ i = 1 N g i = N a i k j ≤ x j < b i k j m i n ∑ i = 1 N x j ? a i k j , j = 1 , 2 , 3 , . . . M f j , g i , k j ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \displaystyle\sum_{i=1}^N g_i = N\\ a_ik_j \le x_j \lt b_ik_j\\ min \displaystyle\sum_{i=1}^N x_j-a_ik_j ,j = 1,2,3,...M\\ f_j , g_i , k_j\in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M \end{cases} ? ? ??ai?gi?≤xj?<bi?gi?i=1∑N?gi?=Nai?kj?≤xj?<bi?kj?mini=1∑N?xj??ai?kj?,j=1,2,3,...Mfj?,gi?,kj?∈{0,1}i=1,2,3,...N,j=1,2,3,...M?

發現模型二實際上就是模型一的改進，模型二利用0/1變量$k_j$去定位藥盒所對應的兩側豎向隔板之間的間隙的同時也是在解決模型一中$ x_j\ge a_i$條件

由此就可以得到一個"通用"的解決手段:
如果出現當$x_i\le a_j$時候某個式子$f(x_i,a_j)$才執行/成立
即$f(x_i,a_j),x_i\le a_j$
假設為$u=\{\begin{array}{l}f(x_i,a_j),x_i\le a_j\\ 0,x_i>a_j\end{array}$
這時候引入一個0/1變量$k_i$
$ \begin{cases}u =f(x_i,a_jk_i)\x_i\le a_jk_j\end{cases}$
但要注意:
1.$f(x_i,a_j)改成f(x_i,a_j{k}_i)$時候不能改變題目本意
2.之所以是$f(x_i,a_j{k}_i)$而不是$f(x_i,a_j)k_i$,是因為最好不出現決策變量和決策變量相乘
3.如果非要用$f(x_i,a_j)k_i$，需要將決策變量和決策變量相乘的模型重新轉化為線性模型

問題三

儲藥柜的寬度不超過2.5m、高度不超過2m，傳送裝置占用的高度為0.5m，即儲藥柜的最大允許有效高度為1.5m。
假設已知所有盒裝藥品所需的儲藥槽寬度$x$約束,和所有盒裝藥品總數$N$
即$a_i<x_i<b_i,i=1,2,\mathrm{3...}N$
假設已知所有盒裝藥品所需的儲藥槽高度度$y$約束,和所有盒裝藥品總數$N$
即$c_i<y_i<d_i,i=1,2,\mathrm{3...}N$
則:
儲藥柜的寬度不超過2.5m
$\sum _{i=1}^N{x}_i\le 2500$
儲藥柜的最大允許有效高度為1.5m
$\sum _{i=1}^N{y}_i\le 1500$

在問題二中寬度冗余為$\sum _{i=1}^N{x}_j?a_i{k}_j$
同理我們也可以得到高度冗余為$\sum _{i=1}^N{y}_j?c_i{l}_j$
平面冗余＝高度冗余×寬度冗余
即平面冗余為$(\sum _{i=1}^N{x}_j?a_i{k}_j)(\sum _{i=1}^N{y}_j?c_i{l}_j)$

要使橫向隔板間距的類型數量也盡可能地少。我們可以利用問題一中的模型求出橫向隔板間距的類型數量臨界值$M_2$

{ a i g i ≤ x j < b i g i ∑ i = 1 N g i = N c i o i ≤ y k < d i o i ∑ i = 1 N o i = N a i h j ≤ x j < b i h j a i l k ≤ y k < b i l k m i n ( ∑ i = 1 N x j ? a i h j ) ( ∑ i = 1 N y k ? c i l k ) , j = 1 , 2 , 3 , . . . M f j , g i , h j , o i , l k ∈ { 0 , 1 } i = 1 , 2 , 3 , . . . N , j = 1 , 2 , 3 , . . . M , k = 1 , 2 , 3 , . . . K \begin{cases} a_ig_i \le x_j \lt b_ig_i\\ \displaystyle\sum_{i=1}^N g_i = N\\ c_io_i\le y_k\lt d_io_i\\ \displaystyle\sum_{i=1}^N o_i = N\\ a_ih_j \le x_j \lt b_ih_j\\ a_il_k \le y_k \lt b_il_k\\ min (\displaystyle\sum_{i=1}^N x_j-a_ih_j)(\displaystyle\sum_{i=1}^N y_k-c_il_k) ,j = 1,2,3,...M\\ f_j , g_i , h_j , o_i ,l_k\in \set{0,1}\\ i = 1,2,3,...N , j = 1,2,3,...M ,k = 1,2,3,...K \end{cases} ? ? ??ai?gi?≤xj?<bi?gi?i=1∑N?gi?=Nci?oi?≤yk?<di?oi?i=1∑N?oi?=Nai?hj?≤xj?<bi?hj?ai?lk?≤yk?<bi?lk?min(i=1∑N?xj??ai?hj?)(i=1∑N?yk??ci?lk?),j=1,2,3,...Mfj?,gi?,hj?,oi?,lk?∈{0,1}i=1,2,3,...N,j=1,2,3,...M,k=1,2,3,...K?

問題四

已知第$i$種藥品編號對應的最大日需求量為$e_i$和該藥盒長度為$z_i$毫米
在儲藥槽的長度為1.5m、每天僅集中補藥一次的情況下，計算每一種藥品需要的儲藥槽個數$x_i$.
$\frac{2?1500}{e_i?z_i}\le x_i$
這樣就得出了所有藥品對應所需儲藥槽個數$x_i$。
在問題三中得出了一個藥柜中所有橫向(豎向)隔板間距的類型大小以及數量
同問題二從模型一到模型二的分組思路，每個藥品其實對應一個組別
可以得出第$i$種藥品對應的組號$m_i$,并且也知道組號$m_i$對應的儲藥槽的個數${\sigma }_{m_i}$

假設有$M$組,$x_{ji}$表示第$j$組第$i$種藥品對應所需儲藥槽個數，${\sigma }_j$表示一個藥柜種組號$j$對應的儲藥槽的個數。
得到問題模型:
$min(ma{x}_{j=1}^M\frac{\sum _{i=1}^{N_j}{x}_{ji}}{{\sigma }_j})$

解決問題

問題一

模型一

在此之前已經初始化藥盒長寬高分別放進數組length,weight,height中
處理一下數據,得到模型一的$a_i$和$b_i$,并且得到$y_j$的所以可能取值
C++

void solve(){outFile.open("data.xlsx");if (!outFile.is_open()) {std::cerr << "無法打開文件" << std::endl;return ;}set<double>y;double a[N],b[N];for(int i=1;i<=1919;i++){a[i] = 2+weight[i];y.insert(a[i]);b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});y.insert(b[i]);}for(int i=1;i<=1919;i++){outFile << a[i] << '\t';}outFile << '\n';for(int i=1;i<=1919;i++){outFile << b[i] << '\t';}outFile << '\n';for(auto x:y){outFile << x << '\t';}
}

這樣我們就完成了上面講的先求出所有可能為豎向隔板間距類型的大小

線性化:

void solve(){outFile.open("data.xlsx");if (!outFile.is_open()) {std::cerr << "無法打開文件" << std::endl;return ;}set<double>y;double a[N],b[N];for(int i=1;i<=1919;i++){a[i] = 2+weight[i];y.insert(a[i]);b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});if((long long)b[i] == b[i])b[i]--;b[i] = (int)b[i];}for(int i=1;i<=1919;i++){outFile << a[i] << '\t';}outFile << '\n';for(int i=1;i<=1919;i++){outFile << b[i] << '\t';}outFile << '\n';cout << (int)y.size();for(auto x:y){outFile << x << '\t';}
}

解決模型一:

sets:aa/1..1919/:a,b;bb/1..47/:f,y;cc(aa,bb):g;
endsets
data:a=@ole("D:\homewrok\建模\儲藥柜的設計問題\data.xls",A1:BUU1);b=@ole("D:\homewrok\建模\儲藥柜的設計問題\data.xls",A2:BUU2);y=@ole("D:\homewrok\建模\儲藥柜的設計問題\data.xls",A3:AU3);
enddata
min=@sum(bb(j):f(j));
@for(aa(i):@for(bb(j):a(i)*g(i,j)<y(j)*f(j)));
@for(aa(i):@for(bb(j):b(i)+58*(1-g(i,j))>y(j)*f(j)));
@for(aa(i):@sum(bb(j):g(i,j))>1);
@for(cc(i,j):@bin(g(i,j)));
@for(bb(j):@bin(f(j)));

解得

  Global optimal solution found.Objective value:                              4.000000Objective bound:                              4.000000Infeasibilities:                              0.000000Extended solver steps:                               0Total solver iterations:                            13Variable           Value        Reduced CostF( 7)        1.000000            1.000000F( 22)        1.000000            1.000000F( 33)        1.000000            1.000000F( 47)        1.000000            1.000000

對應類型長度為:
18,33,44,58

模型二求解

C++預處理數據

void solve(){outFile.open("data2.xlsx");if (!outFile.is_open()) {std::cerr << "無法打開文件" << std::endl;return ;}double a[N],b[N];for(int i=1;i<=1919;i++){a[i] = 2+weight[i];b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});b[i] = (int)(b[i]+0.5);}for(int i=1;i<=1919;i++){for(int j=12;j<=58;j++){int flag = a[i]<j&&j<b[i];outFile << flag << '\t';}outFile << '\n';}
}

sets:aa/1..1919/:;bb/1..47/:f;cc(aa,bb):d;
endsets
data:d = @ole("D:\homewrok\建模\儲藥柜的設計問題\data2.xls",A1:AU1919);
enddata
min=@sum(bb(j):f(j));
@for(aa(i):@sum(bb(j):d(i,j)*f(j))>1);
@for(bb(j):@bin(f(j)));

得到

  Global optimal solution found.Objective value:                              4.000000Objective bound:                              4.000000Infeasibilities:                              0.000000Extended solver steps:                               0Total solver iterations:                            58Variable           Value        Reduced CostF( 8)        1.000000            1.000000F( 23)        1.000000            1.000000F( 33)        1.000000            1.000000F( 47)        1.000000            1.000000

對應類型長度為:
19,34,44,58

純編程求解:

問題一轉換:給出1919個范圍$[a_i,b_i]$，問最少取多少個點使得每個范圍內至少有一個點

vector<pair<int,int>>v(1919);
void solve(){double a[N],b[N];for(int i=1;i<=1919;i++){a[i] = 2+weight[i];b[i] = min({2.0*weight[i],sqrt(weight[i]*weight[i] + height[i]*height[i]), sqrt(weight[i]*weight[i] + length[i]*length[i])});if((long long)b[i] == b[i])b[i]--;b[i] = (int)b[i];v[i-1].first = a[i]  , v[i-1].second=b[i];}
}
void solve2(){//貪心 每次未放入取上限最小的上限sort(v.begin(),v.end(),[&](pair<int,int> x, pair<int,int> y){if(x.first == y.first)return x.second < y.second;return x.first < y.first;});int cnt = 0 , start=0 , end;vector<pair<int,int>>ans;while(cnt < 1919){double x = v[start].second;cnt++;bool flag = false;for(int i=start;i<v.size();i++){if(v[i].first>x){end = i-1;flag = true;break;}}if(flag)ans.push_back(make_pair(v[end].first,x));else{ans.push_back(make_pair(v[v.size()-1].first,x));break;}start = end+1;}cout << cnt << '\n';//答案 4 個for(auto x:ans){cout << x.first << ',' << x.second << '\n';}
}

問題二轉換:給出1919個范圍$[a_i,b_i]$，給出最少取多少個點使得每個范圍內至少有一個點，求全部可能取值
注:不知道最小值為4，當新題做

vector<int>ans2;
int now_ans = 47;
int k=0;//不同取值種類數
int main() {solve();sort(v.begin(),v.end(),[&](pair<int,int> x, pair<int,int> y){if(x.first == y.first)return x.second < y.second;return x.first < y.first;});solve2_f(0,1);cout << k;return 0;
}
void solve2_f(int start ,  int cnt){if(cnt > now_ans)return ;for(int i = v[start].second;i>=v[start].first;i--){bool flag = false;for(int j=start;j<v.size();j++){if(v[j].first>i){flag = true;ans2.push_back(i);solve2_f(j,cnt+1);ans2.pop_back();break;}}if(!flag){ans2.push_back(i);for(auto x:ans2)cout << x << ' ';cout << '\n';ans2.pop_back();now_ans = min(now_ans,cnt);}}
}

問題二

純編程求解:

在上一個問題基礎上加個冗余計算即可

void solve2_f(int start ,  int cnt ,int rong){if(cnt > now_ans)return ;for(int i = v[start].second;i>=v[start].first;i--){bool flag = false;int sum = 0;for(int j=start;j<v.size();j++){if(v[j].first>i){flag = true;ans2.push_back(i);solve2_f(j,cnt+1,rong + sum);ans2.pop_back();break;}sum += i-v[j].first;}if(!flag){k++;ans2.push_back(i);for(auto x:ans2)cout << x << ' ';cout << "rong:" << rong;cout << '\n';ans2.pop_back();now_ans = min(now_ans,cnt);}}
}

求解得到最小的有

19 33 44 60 rong:10875
19 33 44 59 rong:10875
19 33 44 58 rong:10875

答案為19,33,44,58
因為最后一個取值沒有計算冗余度，明顯取58時候冗余度是最少的