程序填空题：部分背包问题（贪心法）

设有编号为1、2、…、n的n个物品，它们的重量分别为w1、w2、…、wn，价值分别为v1、v2、…、vn，其中wi、vi（1≤i≤n）均为正数。
　有一个背包可以携带的最大重量不超过W。求解目标：在不超过背包负重的前提下，使背包装入的总价值最大。

```c++
#include
#include
#include
#include
using namespace std;
#define MAXN 51
//问题表示
int n;
double W; //限重
struct NodeType
{ int no;
double w;
double v;
double p; //p=v/w
float x;
bool operator<(const NodeType &s) const
{
return p>s.p; //按p递减排序
}
};
NodeType A[MAXN]={{0}}; //下标0不用
//求解结果表示
double V; //最大价值
bool cmp(const NodeType &a,const NodeType &b)
{
return a.no}

void Knap() //求解背包问题并返回总价值
{
V=0; //V初始化为0
double weight=W; //背包中能装入的余下重量
int i=1;
while ()
{ A[i].x=1; //装入物品i
;
V+=A[i].v; //累计总价值
;
}
if (weight>0) //当余下重量大于0
{ A[i].x=;
V+=A[i].x*A[i].v; //累计总价值
}
}

int main()
{ cin>>n>>W;
for(int i=1;i<=n;i++)
{
cin>>A[i].no>>A[i].w>>A[i].v;A[i].x=0;
}
for (int i=1;i<=n;i++) //求v/w
A[i].p=A[i].v/A[i].w;
sort(A+1,A+n+1); //排序
Knap();
sort(A+1,A+n+1,cmp);
for(int j=1;j<=n;j++)
cout< cout< return 0;
}
```

### 输入格式:
第一行物品数n和背包容量W，接着的n行中输入每个物品的编号，重量和价值。

### 输出格式:
输出装入背包的物品信息，共n行，按物品编号递增排序的物品编号及重量（物品编号从1开始）。最后一行输出总价值。

### 输入样例1:

```in
5 100
1 10 20
2 20 30
3 30 66
4 40 40
5 50 60
```

### 输出样例1:

```out
1 20
2 30
3 66
4 0
5 48
164
```






答案：
第1空：A[i].w<=weight

第2空：weight-=A[i].w

第3空：i++

第4空：weight/A[i].w