問題描述
在北美洲東南部，有一片神秘的海域，那里碧海藍天、陽光明媚，這正是傳說中海盜最活躍的加勒比海(Caribbean Sea)，17 世紀時，這里更是歐洲大陸的商旅艦隊到達美洲的必經之地，所以當時的海盜活動非常猖獗，海盜不僅攻擊過往商人，甚至攻擊英國皇家艦.....
有一天，海盜們截獲了一艘裝滿各種各樣古董的貨船，每一件古董都價值連城，一旦打碎就失去了它的價值，雖然海盜船足夠大，但載重量為C,每件古董的重量為w【i】;,海盜們該如何把盡可能多數量的寶貝裝上海盜船呢?
演算法設計
【1】由于題目中并沒有描述每件古董的價值有多高，只說每一件古董都價值連城，所以我們直接認為每一件古董的價值都基本相等
【2】因此盡管可能古董的價值有差，當數量占優勢的時候，這些差異也就相比之下可以忽略不計了
【3】當載重量為定值C時，W【i】越小時，可裝載的古董數量n越大，只要依次選擇最小重量古董，直到不能再裝為止
【4】把n個古董的重量從小到大【非遞減】排序，然后根據貪心策略盡可能多地選出前i個古董，直到不能繼續裝為止，此時達到最優
假設每個古董重量如表中所示，海盜船的載重量c為30
| 重量w[i] | 4 | 10 | 7 | 11 | 3 | 5 | 14 | 2 |
【1】因為貪心策略是每次選擇重量最小的古董裝入海盜船，因此可以按照古董重量非遞減順序排序，排序后
| 重量w[i] | 2 | 3 | 4 | 5 | 7 | 10 | 11 | 14 |
【2】按照貪心策略，每次選擇重量最小的古董放入【tmp代表古董的重量，ans代表已裝載的古董個數】
i=0， 選擇排序后的第1個，裝入重量tmp=2， 不超過載重量30， ans=1，
i=1，選擇排序后的第2個，裝入重量tmp= 2+3=5， 不超過載重量30，ans =2，
i=2， 選擇排序后的第3個，裝入重量tmp=5+4=9， 不超過載重量30， ans =3，
i=3，選擇排序后的第4個，裝入重量tmp=9+5=14，不超過載重量30，ans=4，
i=4，選擇排序后的第5個，裝入重量tmp=14+7=21， 不超過載重量30，ans=5，
i=5， 選擇排序后的第6個，裝入重量tmp=21+10=31， 超過載重量30， 演算法結束，
即放入古董的個數為ans=5個，
偽代碼設計
【1】資料結構定義 double w[n]
【2】按照重量排序 sort（）
【3】按照貪心策略找最優解
Java語言實作
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
double w[]= {4,10,7,11,3,5,14,2};
Arrays.sort(w);
int ans=0;
int tmp=0;
for(int i=0;i<w.length;i++) {
tmp+=w[i];
if(tmp<30) {
ans++;
}
}
System.out.println("最后取得的寶物數量為："+ans);
}
}
演算法復雜度
時間復雜度：
【1】按照古董重量排序，呼叫sort函式，平均時間復雜度為O(nlogn)
【2】for回圈時間復雜度為O(n)
【3】時間復雜度為O(nlogn+n)
空間復雜度：O(1)
在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖， 我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在， 我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/452032.html
標籤：其他
下一篇：靜態鏈路聚合方案