这个题目如果直接在sort中比较 Ji / Fi 会出现RUNTIME ERROR 因为 分母不能为 0 ,这里在输入时直接将它算出来用weight 表示
贪心策略:weight最大的
1
#include <iostream>
2
using namespace std;
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
struct food
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
6
int ji;
7
int fi;
8
double weight;
9
}a[1001];
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*int cmp (const void *a, const void *b)
12
{
13
return (*((food *)a)).weight < (*((food *)b)).weight;
14
}*/
15![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
16
bool cmp1 (const food &a, const food &b)
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
18
return a.weight > b.weight;
19
}
20![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
21
int main ()
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
23
int m, n;
24
while ( scanf ("%d %d", &m, &n) != EOF && (m != -1 && n != -1))
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
26
double sum = 0;
27
//输入处理
28
for (int i = 0; i < n; i ++)
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
41
printf ("%d %d\n", a[i].ji, a[i].fi);
42
}
43
44
//求的最大量的食物
45
for (int i = 0; i < n; i ++)
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
47
if ( m >= a[i].fi)
48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
49
m -= a[i].fi;
50
sum += a[i].ji;
51
}
52
else if ( m < a[i].fi )
53![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2010-08-24 18:41
雪黛依梦 阅读(693)
评论(0) 编辑 收藏 引用 所属分类:
背包----贪心、回溯、分支界限