装船问题

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
价重比：计算其价值与重量之比
Author
 
01
#include<stdio.h>
02
struct huo
03
{
04
    int w, p;
05
    double b;
06
} a[10], t;
07
int main()
08
{
09
    int i, m, k, sum, j;
10
    scanf("%d", &m);
11
    for(i = 0; i < 10; i++)
12
    {
13
        scanf("%d%d", &a[i].p, &a[i].w);
14
        a[i].b = a[i].p / a[i].w;
15
    }
16
    for(i = 0; i < 9; i++)
17
    {
18
        k = i;
19
        for(j = i + 1; j < 10; j++)
20
        {
21
            if(a[i].b < a[j].b)
22
                k = j;
23
        }
24
        if(k != i)
25
        {
26
            t = a[i];
27
            a[i] = a[k];
28
            a[k] = t;
29
        }
30
    }
31
    i = 0;
32
    sum = 0;
33
    while(m > 0)
34
    {
35
        if(m > a[i].w)
36
        {
37
            sum += a[i].p;
38
            m -= a[i].w;
39
        }
40
        else
41
        {
42
            sum += a[i].b * m;
43
            m -= a[i].w;
44
        }
45
        i++;
46
    }
47
    printf("%d/n", sum);
48
    return 0;
49
}