這個題目如果直接在sort中比較 Ji / Fi 會出現(xiàn)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 的 貓食能夠得到最大數(shù)量的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
雪黛依夢 閱讀(715)
評論(0) 編輯 收藏 引用 所屬分類:
背包----貪心、回溯、分支界限