題目描述：

產(chǎn)品由n個部件組成（n〈= 100），每個部件有b和p 兩個屬性值，每個部件有m種選擇（m〈=100），總產(chǎn)品的B=min{bi} ，P=Σ{pi}，選擇各部件，使得最后產(chǎn)品的B/P值最大。

解題思路:

貪心。思路(來自Discuss)

1,獲得一個最小和最大帶寬:

    最小帶寬是各個設(shè)備最小帶寬的最大值,

    最大帶寬是各個設(shè)備最大帶寬的最小值.

2,從最小值遞增到最大值進(jìn)行尋找,

計算各種設(shè)備價錢的最小值的和,然后計算出一個比值,

如果比值比當(dāng)前比值大,更換當(dāng)前比值;

3,重復(fù)2直到結(jié)束.

/*

for(i=0;i<總共的狀態(tài)數(shù);i++)

{     for (j=0;j<總的部件數(shù);j++)

       {     for(k=0;k<總的選擇;k++)

                     求出滿足狀態(tài)i的，p值最小的部件;

           total+=求出來的p；

     }

     比較求出最大的B[i]/ total 的值；

}

*/

 1/** *//********************************************************************
 2Author: littlekid
 3Created Time: 2007-11-28
 4Problem Source: POJ1018
 5Description: 
 6********************************************************************/
 7# include <stdio.h>
 8
 9# define N 110
10# define MAX 342289
11
12int b[ N ][ N ],p[ N ][ N ];
13int m[ N ];
14
15int main()
16{
17    int n;
18    int min_b, max_b;
19    int sum_p, min_p;
20    double max;
21    int T; scanf( "%d", &T );
22    while ( T -- )
23    {
24        max_b = 0; min_b = MAX;
25        scanf("%d",&n);
26        for( int i = 0; i < n; ++ i)
27        {
28            scanf( "%d", &m[i] );
29            for( int j = 0; j < m[ i ]; ++ j )
30            {
31                scanf( "%d %d", &b[ i ][ j ], &p[ i ][ j ] );
32                if ( max_b < b[ i ][ j ] ) max_b = b[ i ][ j ];
33                if ( min_b > b[ i ][ j ] ) min_b = b[ i ][ j ];
34            }
35        }
36        max = 0.00;
37        for( int i = min_b; i <= max_b; ++ i)
38        {
39            sum_p = 0;
40            for( int j = 0; j < n; ++ j)
41            {
42                min_p = MAX;
43                for( int k = 0; k < m[ j ]; ++ k )
44                {
45                    if( b[ j ][ k ] >= i && p[ j ][ k ] < min_p )
46                    {
47                        min_p = p[ j ][ k ];
48                    }
49                }
50                sum_p += min_p;
51            }
52            if( (double)i / (double)sum_p > max ) 
53            {
54                max = (double)i / (double)sum_p;
55            }
56        }
57        printf( "%.3lf\n", max );
58    }
59    return 0;
60}
61