题目描述:
产品由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
3
Created Time: 2007-11-28
4
Problem Source: POJ1018
5
Description:
6
********************************************************************/
7
# include <stdio.h>
8
9
# define N 110
10
# define MAX 342289
11
12
int b[ N ][ N ],p[ N ][ N ];
13
int m[ N ];
14
15
int 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 阅读(1524)
评论(3) 编辑 收藏 引用 所属分类:
Problem Solving