题目来自:圣诞老人的礼物(贪心算法)
#include<stdio.h>
#include<string.h>
#define Max 105
//candies结构体
struct candy
{
int v;//value
int w;//weight
}candies[Max];
//排序函数(注意两种数列一起上参数的用法)
void bubbleSort(double a[],struct candy b[],int len)
{
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1])
{
struct candy temp = candies[j];
candies[j] = candies[j + 1];
candies[j + 1] = temp;
}
}
}
}
int main()
{
int n, w;
double res;
while (scanf("%d%d", &n, &w) != EOF)//读入(输入样例第一行)
{
double res = 0;//每次循环初始化result
double vw[Max];//单位价值v/m
for (int i = 0; i < n; i++) //循环n次读入糖果的w,v
{
scanf("%d%d", &candies[i].v, &candies[i].w);
}
//记录v/m
for (int i = 0; i < n; i++)
{
vw[i] = candies[i].v*1.0 / candies[i].w;
}
//按照v/w的性价比由低到高排序(vm数组的len就是n)
bubbleSort(vw,candies,n);
for (int i = n-1; i >=0; i--)
{
if (candies[i].w < w)
{
res += candies[i].v;
w -= candies[i].w;
//测试代码
printf("%d\n",candies[i].v);
}
else
{
res += (candies[i].v*1.0 /candies[i].w) * w;//不足部分将部分取走
break;
}
}
printf("%.1lf\n",res);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define Max 105
//candies结构体
struct candy
{
int v;//value
int w;//weight
}candies[Max];
//排序函数(注意两种数列一起上参数的用法)
void bubbleSort(double a[],struct candy b[],int len)
{
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1])
{
struct candy temp = candies[j];
candies[j] = candies[j + 1];
candies[j + 1] = temp;
}
}
}
}
int main()
{
int n, w;
double res;
while (scanf("%d%d", &n, &w) != EOF)//读入(输入样例第一行)
{
double res = 0;//每次循环初始化result
double vw[Max];//单位价值v/m
for (int i = 0; i < n; i++) //循环n次读入糖果的w,v
{
scanf("%d%d", &candies[i].v, &candies[i].w);
}
//记录v/m
for (int i = 0; i < n; i++)
{
vw[i] = candies[i].v*1.0 / candies[i].w;
}
//按照v/w的性价比由低到高排序(vm数组的len就是n)
bubbleSort(vw,candies,n);
for (int i = n-1; i >=0; i--)
{
if (candies[i].w < w)
{
res += candies[i].v;
w -= candies[i].w;
//测试代码
printf("%d\n",candies[i].v);
}
else
{
res += (candies[i].v*1.0 /candies[i].w) * w;//不足部分将部分取走
break;
}
}
printf("%.1lf\n",res);
}
return 0;
}