- 搜標(biāo)題
- 搜題干
- 搜選項
問答題
【簡答題】在0-1背包問題中，若各物品依重量遞增序排列時，其價值恰好依遞減序排列，對這個特殊的0-1背包問題，設(shè)計一個有效的算法找出最優(yōu)解。（描述你的算法即可，無需證明算法的正確性）
答案：
對于0－1背包問題本來是無法用貪心算法得到最優(yōu)解的，但對于這類特殊的0－1背包問題，則可以用貪心算法去解。貪心策略如下：...
你可能感興趣的試題
問答題
【簡答題】
Olay教授正在為一家石油公司咨詢，該公司正在計劃建造一條由東向西的石油主管道，該管道要穿過一片有n口井的油田，從每口井中都有一條噴油管沿最短路徑與主管道直接相連（噴油管道為南北方向）。
給定各個井的X坐標(biāo)和Y坐標(biāo)，Olay教授要如何才能選擇最佳主管道的位置（即：使各噴油管長度之和最?。?？
答案：
這是中位數(shù)的應(yīng)用問題。在順序統(tǒng)計的問題中，中位數(shù)的應(yīng)用最廣，例如在X軸上有n個點，由左到右依次排列為X1，X2，&hel...
問答題
【簡答題】在最接近點對問題中，用一條垂直線L：x=m將平面點集分為大致相等的兩個子集S1和S2。設(shè)P1和P2分別表示直線L的左邊和右邊的寬為d的兩個垂直長條區(qū)域，d1和d2分別是S1和S2中最小距離，且設(shè)d=min{d1，d2}。對于P1中任意一個點p，可能和在P2中點q構(gòu)成全平面點集的最接近點對的候選點對，請證明：P2中最多有6對這樣的候選點對。
答案：
根據(jù)鴿籠原理：如果n+1只鴿子飛入n個籠子中，那么至少有一個籠子里包含兩只或兩只以上的鴿子。
將矩形R的長為2...
將矩形R的長為2...
