PRoblem Description

王小二畢業(yè)后從事船運(yùn)規(guī)劃工作，吉祥號貨輪的最大載重量為M噸，有10種貨物可以裝船。第i種貨物有wi噸，總價值是pi。王小二的任務(wù)是從10種貨物中挑選若干噸上船，在滿足貨物總重量小于等于M的前提下，運(yùn)走的貨物的價重比最大。

Input

輸入數(shù)據(jù)的第一行有一個正整數(shù)M(0 < M < 10000)，表示所有貨物最大載重量。在接下來的10行中，每行有若干個數(shù)（中間用空格分開），第i行表示的是第i種貨物的貨物的總價值pi ,總重量wi。(pi是wi的整數(shù)倍，0 < pi , wi < 1000)

Output

輸出一個整數(shù)，表示可以得到的最大價值。

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
}