头歌实训作业 算法设计与分析-贪心算法(第2关：最优装载问题)

任务描述

有一批集装箱要装上一艘载重量为C的轮船，共有n个集装箱，其中集装箱i的重量为Wi。
最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

测试说明
输入和输出说明：
第1行为集装箱数目n和载重限制C
第2行~第n+1行为n个集装箱的重量
输出最优装载方案的集装箱数目，若没有装入任何集装箱，则输出0

输入示例1：
5 10
5
2
6
4
3

输出示例1:
3

说明：
其中一个最优装载方案为
装入重量为2、3和4的集装箱

输入示例2：
2 10
11
12

输出示例2:
0

说明：
集装箱都超重

测试代码： 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//问题表示
int	n, W;			//集装箱数目， 载重限制
vector<int> weight;	//各集装箱重量,不用下标0的元素

//求解结果表示
int maxn;							//存放最优解的集装箱总数目 
vector<int> x;						//存放最优解的各个集装箱装入情况，0不装入，1装入 

void solve()						//贪心算法求解最优装载问题
{

	/* 请在这里填写答案 */
	/**********  Begin  **********/




	/**********  End  **********/ 
}
int main()
{
	cin>>n>>W;
	weight.resize(n);
	for (int i = 0; i < n; i++)
		cin>>weight[i];

	solve();

	cout<<maxn<<endl;
	
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//问题表示
int	n, W;			//集装箱数目， 载重限制
vector<int> weight;	//各集装箱重量,不用下标0的元素

//求解结果表示
int maxn;							//存放最优解的集装箱总数目 
vector<int> x;						//存放最优解的各个集装箱装入情况，0不装入，1装入 

void solve()						//贪心算法求解最优装载问题
{

	/* 请在这里填写答案 */
	/**********  Begin  **********/
    sort(weight.begin(), weight.end());
    maxn=0;
    int rest = W;
    for( int i=0;i<n;i++){
        if(rest >= weight[i]){
            x.push_back(1);
            rest -= weight[i];
            maxn++;
        }
        else{
            x.push_back(0);
        }
    }



	/**********  End  **********/ 
}
int main()
{
	cin>>n>>W;
	weight.resize(n);
	for (int i = 0; i < n; i++)
		cin>>weight[i];

	solve();

	cout<<maxn<<endl;
	
	return 0;
}