程序填空题：求解最优装载问题（贪心法）

有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要选出尽可能多的集装箱装上轮船，使它们的重量之和不超过W。

```c++
#include
#include
#include
#include
using namespace std;
#define MAXN 20 //最多集装箱个数
//问题表示
int n,W;
//求解结果表示
int maxw; //存放最优解的总重量

struct NodeType
{ int no;
int wi;
int x;
bool operator<(const NodeType &s) const
{
return wi }
};
NodeType w[MAXN]={{0}}; //各集装箱重量,不用下标0的元素

bool cmp(const NodeType &a,const NodeType &b)
{
return a.no}

void solve() //求解最优装载问题
{
; //w[1..n]递增排序
maxw=0;
int restw=W; //剩余重量
for (int i=1;;i++)
{
w[i].x=1; //选择集装箱i
restw-=w[i].wi; //减少剩余重量
maxw=;
}
}

int main()
{ cin>>n>>W;
for(int i=1;i<=n;i++)
{
cin>>w[i].no>>w[i].wi;
w[i].x=0;
}
solve();
sort(w+1,w+n+1,cmp);
for (int i=1;i<=n;i++)
if (w[i].x==1)
printf("%d %d\n",w[i].no,w[i].wi);
printf("%d",maxw);
return 0;
}
```
### 输入样例1:

```in
5 10
1 5
2 2
3 6
4 4
5 3
```

### 输出样例1:

```out
2 2
4 4
5 3
9
```





答案：
第1空：sort(w+1,w+n+1)

第2空：i<=n && w[i].wi<=restw

第3空：maxw+w[i].wi