最优装载问题

核心算法

    

    贪心。

问题描述

     

    有 n 个件物品，第 i 个物品的重量为 wi。在不超过最大承载量 C
的范围内，你要选择尽可能多的物品，请问你最多可以选择多少件物
品。

解题步骤

     

输入

按照题意进行输入

排序

对物品的重量进行排序

选择

优先选择重量小的物品

停止

直到装不下下一件物品或装完所有物品停止装箱

输出

输出答案即选择的物品总重量

结束

解题步骤

  


  

//C++
#include<algorithm>
#include<cstdio>
using namespace std;
int w[10005];
int main() { 
    int n,c; 
    scanf('%d%d',&n,&c); //输入物品的件数 最大承载量  
    for(int i = 0; i < n; i++) {  
        scanf('%d',&w[i]); //依次输入 n 个物品的重量  
    } 
    sort(w,w+n); //无比较函数默认从小到大排序  
    int ans = 0; 
    for(int i = 0; i < n; i++) {  
        if(w[i] <= c) { //剩余承载量可以装下 wi 
            ans++; //装下这一件物品   
            c -= w[i]; //剩余承载量减掉当前物品重量    }  
        else { //剩余承载量不足以装下 wi    
            break; //结束循环   
        } 
    } 
    printf('%d\n',ans); //输出答案  
    return 0; 
}

例题推荐

   

    在北美洲东南部,有一片神秘的海域,那里碧海蓝天、阳光明媚,这正是传说中海盗最活跃的加勒比海,这里更是欧洲大陆的商旅舰队到达美洲的必经之地,所以当时的海盗活皇家舰......动非常猖獗,海盗不仅攻击过往商人,甚至攻击英国有一天,海盗们截获了一艘装满各种各样古董的货船,每一件古董都价值连城,一旦打碎就失去了它的价值。虽然海盗船足够大,但载重量为 C,每件古董的重量为 Wi ,海盗们该如何把尽可能多数量的宝贝装上海盗船呢？