2623: 贪心算法-背包问题
金币值：3
定数：6
时间限制：1.000 s
内存限制：128 M
正确：6
提交：7
正确率：85.71% 命题人：
题目描述
给定n(1<=x<=20)种不同的物品和一背包。物品i (1≤i≤n) 的重量是wi (wi 是大于 0的整数)，其价值为vi(vi 是大于 0的整数)，背包的容量为c (c 是大于 0的整数)。问应如何选择装入背包的物品(可以装入某个物品的一部分)，使得装入背包中物品的总价值最大? 假设两个物品的价值重量之比相等则优先选择编号小的物品。
测试代码 复制
#include <stdio.h>
struct good {
int w,v,id; //w,v,id分别表示物品的重量,价值和编号
double x; //x在0-1之间取值，表示该物品需要放多少到背包中
double ratio; //单位重量的价值
};
void f(struct good goods[],int n,int c) {
for(int i=1; i<=n; i++) {
}
}
void sort(struct good goods[],int n) {
for(int i=1; i<=n-1; i++) { ///冒泡排序(降序)
for(int j=1; j<=n-i; j++) {
if(goods[j].ratio<goods[j+1].ratio) {
struct good temp;
temp=goods[j];
goods[j]=goods[j+1];
goods[j+1]=temp;
}
}
}
}
int main(void) {
int i,n,c;
struct good goods[21]; //0号单元不存储有效数据
scanf("%d %d", &n,&c);
for(i=1; i<=n; i++) {
scanf("%d", &goods[i].w);
}
for(i=1; i<=n; i++) {
scanf("%d", &goods[i].v);
}
for(i=1; i<=n; i++) {
goods[i].id=i;
goods[i].x=0;
goods[i].ratio=1.0*goods[i].v/goods[i].w;
}
sort(goods,n);
f(goods,n,c);
for(i=1; i<=n; i++) {
printf("%d %.2f\n",goods[i].id,goods[i].x);
}
return 0;
}输入格式
第一行输入物品的个数以及背包的容量n和c
第二行输入每个物品的重量
第三行输入每个物品的价值
第二行输入每个物品的重量
第三行输入每个物品的价值
输出格式
输出n行，每行有两个数，第一个整数表示物品的编号（物品的编号按贪心选择的顺序输出），第二个实数表示对应物品的取舍情况（保留两位小数）
输入样例 复制
4 50
20 30 10 5
100 120 60 2输出样例 复制
3 1.00
1 1.00
2 0.67
4 0.00