装船问题

PRoblem Description

王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有10种货物可以装船。第i种货物有wi吨，总价值是pi。王小二的任务是从10种货物中挑选若干吨上船，在满足货物总重量小于等于M的前提下，运走的货物的价重比最大。

Input

输入数据的第一行有一个正整数M(0 < M < 10000)，表示所有货物最大载重量。在接下来的10行中，每行有若干个数（中间用空格分开），第i行表示的是第i种货物的货物的总价值pi ,总重量wi。(pi是wi的整数倍，0 < pi , wi < 1000)

Output

输出一个整数，表示可以得到的最大价值。

Example Input

10010 1020 1030 1040 1050 1060 1070 1080 1090 10100 10
Example Output
550
Hint
价重比：计算其价值与重量之比
C++
#include<stdio.h>#include<algorithm>    using namespace std;    struct node    {      int p;      int w;      int bi;    }size[10];    int cmp(node a,node b)    {      return a.bi>b.bi;    }    int main()    {      int m,i,sum,flag;      scanf("%d",&m);         sum=0;flag=0;         for(i=0;i<10;i++)         {            scanf("%d%d",&size[i].p,&size[i].w);            size[i].bi=size[i].p/size[i].w;         }         sort(size,size+10,cmp);        for(i=0;i<10;i++)        {            if(flag<m)            {                sum+=size[i].p;                flag+=size[i].w;            }            else if(flag==m)            {                break;            }            else            {                flag=flag-size[i-1].w;                sum=sum-size[i-1].p;                sum=sum+(m-flag)*size[i-1].bi;                break;            }        }        printf("%d/n",sum);       return 0;    }
   C
#include<stdio.h>struct node{      int p;      int w;      int bi;}size[10],t;int main(){    int m,sum,flag,i,j;    scanf("%d",&m);        sum=0;        flag=0;        for(i=0;i<10;i++)        {            scanf("%d %d",&size[i].p,&size[i].w);            size[i].bi=size[i].p/size[i].w;        }        for(i=0;i<10;i++)        {            for(j=0;j<9-i;j++)            {                if(size[j].bi<size[j+1].bi)                {                    t=size[j],size[j]=size[j+1],size[j+1]=t;                }            }        }        for(i=0;i<10;i++)        {            if(flag<m)            {                sum+=size[i].p;                flag+=size[i].w;            }            else if(flag==m)            {                break;            }            else            {                flag=flag-size[i-1].w;                sum=sum-size[i-1].p;                sum=sum+(m-flag)*size[i-1].bi;                break;            }        }            printf("%d/n",sum);    return 0;}