一群海盜截獲了一艘裝滿各種金銀珠寶和古董的貨船，每一件寶物都價值連城一旦打碎就失去了價值。海盜船的載重量為C，每件寶物的重量為Wi，海盜們應該如何把盡可能多的寶物裝上船？

根據(jù)算法設計分析，我們用一維數(shù)組

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=100005;
double w[N];

int main(){
    double c=0;//載入重量C
    int n=0;//古董個數(shù)n
    printf("請輸入船只的載重量C，和古董數(shù)量N：");
    scanf("%d %d",&c,&n); 
    printf("請輸入每個古董的重量");   
    for(int i = 0; i < n; i++){
        scanf("%d",&w[i]);
    }
    sort(w,w+n);//按照古董重量升序排列 
    double tmp=0;//tmp為已裝載的古董重量 
    int ans=0;  //ans為已經(jīng)裝上的古董個數(shù) 
    for(int i=0;i<n;i++){
        tmp += w[i];
        if(tmp<=c){
            ans++;
        }
        else{
            break;
        }
    }
    printf("能裝進去的古董最大數(shù)目為%d",ans);   
    return 0;
} 

算法復雜度分析：
時間復雜度：按照重量排序，調用sort函數(shù)，其平均時間復雜度為O（nlogn），輸入和貪心策略求解的兩個for語句時間復雜度均為O（n），所以時間復雜度為O（n+nlog（n））
空間復雜度：程序中變量tmp,ans等占用了一些輔助空間，這些輔助空間都是常熟階的，因此空間復雜度為O（1）。

    for(int i=0;i<n;i++){
        tmp += w[i];
        if(tmp>=c){
                  if(tmp==c)
                ans = i +1;
                      else
                ans =1;
        break;
        }
    }