0/1背包问题

0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求而且重量和恰好为W具有最大的价值。

输入格式:

第一行输入背包载重量W及背包个数n，再依次输入n行，每行为背包重量wi和价值vi。

输出格式:

第一行输出装入背包内的物体编号(末尾有空格),若没有任何物品能装入，输出: No，第二行输出背包内的物体总价值。

输入样例1:

5 10
2 6
2 3
6 5
5 4
4 6

输出样例1:

1 2 5 
15

输入样例2:

2 10
11 2
13 100

输出样例2:

No
0

//贪心算法，利用其价值密度，结合结构体和cmp进行排序，再用个变量记住它以前的位置 

#include<bits/stdc++.h>
using namespace std;
struct xx{
    int w,v,y;double x;
}s[105];
bool cmp(xx a,xx b){
    return a.x<b.x;
}
int main(){
    int n,m,i,c=0,d=0,e[105],k=0;
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>s[i].w>>s[i].v;
        s[i].x=s[i].v*1.0/s[i].w;
        s[i].y=i;
    }
    sort(s,s+n,cmp);
    for(i=n-1;i>=0;i--){
         if(s[i].w<=m){m-=s[i].w;c+=s[i].v;d=1;e[k++]=s[i].y+1;}
    }if(d==1)
   { sort(e,e+k);
    for(i=0;i<k;i++)cout<<e[i]<<' ';
    cout<<endl<<c;}
    else cout<<"No\n0";
    return 0;
}