問(wèn)答題

【簡(jiǎn)答題】在最接近點(diǎn)對(duì)問(wèn)題中，用一條垂直線L：x=m將平面點(diǎn)集分為大致相等的兩個(gè)子集S1和S2。設(shè)P1和P2分別表示直線L的左邊和右邊的寬為d的兩個(gè)垂直長(zhǎng)條區(qū)域，d1和d2分別是S1和S2中最小距離，且設(shè)d=min{d1，d2}。對(duì)于P1中任意一個(gè)點(diǎn)p，可能和在P2中點(diǎn)q構(gòu)成全平面點(diǎn)集的最接近點(diǎn)對(duì)的候選點(diǎn)對(duì)，請(qǐng)證明：P2中最多有6對(duì)這樣的候選點(diǎn)對(duì)。

答案：根據(jù)鴿籠原理：如果n+1只鴿子飛入n個(gè)籠子中，那么至少有一個(gè)籠子里包含兩只或兩只以上的鴿子。
將矩形R的長(zhǎng)為2...

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】
對(duì)于符號(hào)三角問(wèn)題，符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)可以為“＋”或“－”，以下每一行的符號(hào)由上行得到，2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“－”。如下圖所示（第一行有4個(gè)符號(hào)的符號(hào)三角中的其中的一個(gè)）：

請(qǐng)畫出使用回溯法求解第一行有4個(gè)符號(hào)（即n＝4）時(shí)，解空間樹(shù)的形狀。

答案：

第一行4個(gè)符號(hào)（即n＝4）時(shí)，解空間樹(shù)是一棵完全二叉樹(shù)。

問(wèn)答題

【計(jì)算題】
對(duì)于如下描述的背包問(wèn)題，請(qǐng)計(jì)算最終裝入背包的最大價(jià)值和以及各個(gè)物品裝入背包的數(shù)量。
背包容量：C＝50千克。3件物品。物品1重20千克，價(jià)值100元；物品2重20千克，價(jià)值120元；物品3重30千克，價(jià)值90元。

答案：物品1的單位重量?jī)r(jià)值為50元/千克；物品2的單位重量?jī)r(jià)值為60元/千克；物品3的單位重量?jī)r(jià)值為30元/千克。采用貪心算法...