这个题目如果直接在sort中比较 Ji / Fi 会出现RUNTIME ERROR 因为 分母不能为 0 ，这里在输入时直接将它算出来用weight 表示
贪心策略：weight最大的
1
#include <iostream>
2using namespace std;
3
4struct food
5
{
6
int ji;
7 int fi;
8 double weight;
9
}a[1001];
10
11/**//*int cmp (const void *a, const void *b)
12{
13 return (*((food *)a)).weight < (*((food *)b)).weight;
14}*/
15
16bool cmp1 (const food &a, const food &b)
17{
18 return a.weight > b.weight;
19}
20
21int main ()
22{
23 int m, n;
24 while ( scanf ("%d %d", &m, &n) != EOF && (m != -1 && n != -1))
25
{
26 double sum = 0;
27 //输入处理
28 for (int i = 0; i < n; i ++)
29 {
30 scanf ("%d %d", &a[i].ji, &a[i].fi);
31 a[i].weight = (1.0 * a[i].ji) / a[i].fi;
32
}
33
34 printf ("\n");
35 //按每个房间 1 的 猫食能够得到最大数量的Javabeans排序
36 //qsort (a, n, sizeof(a[0]), cmp);
37 sort (a, a + n, cmp1);
38
39 for (int i = 0; i < n; i ++)
40 {
41 printf ("%d %d\n", a[i].ji, a[i].fi);
42 }
43
44 //求的最大量的食物
45 for (int i = 0; i < n; i ++)
46 {
47 if ( m >= a[i].fi)
48 {
49 m -= a[i].fi;
50 sum += a[i].ji;
51 }
52 else if ( m < a[i].fi )
53 {
54 sum += ( m * (1.0 * a[i].ji / a[i].fi ) ); //猫食不够了
55 break;
56 }
57 }
58
59 printf ("%.3f\n", sum);
60 }
61 // system ("pause");
62 return 0;
63}
64
posted on 2010-08-24 18:41
雪黛依梦 阅读(709)
评论(0) 编辑 收藏 引用 所属分类:
背包----贪心、回溯、分支界限