題目描述：
產品由n個部件組成（n〈= 100），每個部件有b和p 兩個屬性值，每個部件有m種選擇（m〈=100），總產品的B=min{bi} ，P=Σ{pi}，選擇各部件，使得最后產品的B/P值最大。
解題思路:
貪心。思路(來自Discuss)
1,獲得一個最小和最大帶寬:
最小帶寬是各個設備最小帶寬的最大值,
最大帶寬是各個設備最大帶寬的最小值.
2,從最小值遞增到最大值進行尋找,
計算各種設備價錢的最小值的和,然后計算出一個比值,
如果比值比當前比值大,更換當前比值;
3,重復2直到結束.
/*
for(i=0;i<總共的狀態數;i++)
{ for (j=0;j<總的部件數;j++)
{ for(k=0;k<總的選擇;k++)
求出滿足狀態i的，p值最小的部件;
total+=求出來的p；
}
比較求出最大的B[i]/ total 的值；
}
*/
1
/** *//********************************************************************
2
Author: 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
posted on 2007-12-01 23:10
R2 閱讀(1526)
評論(3) 編輯 收藏 引用 所屬分類:
Problem Solving