帮我写一个c语言的贪心算法
时间: 2023-03-27 08:01:35 浏览: 57
好的,我可以为您提供一个贪心算法的示例代码,如下:
#include <stdio.h>
#define MAX_N 100
int n; // 物品数量
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品价值
// 按照单位价值排序
void sort() {
int i, j;
for (i = ; i < n; i++) {
for (j = i + 1; j < n; j++) {
double vi = (double)v[i] / w[i];
double vj = (double)v[j] / w[j];
if (vi < vj) {
int tmp = w[i];
w[i] = w[j];
w[j] = tmp;
tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
}
}
}
// 贪心算法
double greedy(int c) {
sort();
double ans = ;
int i;
for (i = ; i < n; i++) {
if (c >= w[i]) {
ans += v[i];
c -= w[i];
} else {
ans += (double)v[i] / w[i] * c;
break;
}
}
return ans;
}
int main() {
int c; // 背包容量
scanf("%d%d", &n, &c);
int i;
for (i = ; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
double ans = greedy(c);
printf("%.2f\n", ans);
return ;
}