贪心算法装载问题C语言
时间: 2023-12-03 15:39:25 浏览: 44
这是一个经典的贪心算法问题,也称为背包问题。其思路是先将所有物体按重量从小到大排序,然后依次选择重量较小的物体,直到所选物体的总重量超过所允许的最大重量C。以下是C语言的实现代码:
```c
#include <stdio.h>
#include <algorithm>
using namespace std;
const int a=1005;
int n,C; //n个物体,最大载重量为C
int w[a]; //第i个物体的重量
char ans[a]; //记录每个物体是否被选中
int main(){
int i;
int num=0;
int sum=0;
printf("请分别输入物体的数量和装载总重量(用逗号隔开):");
scanf("%d,%d",&n,&C);
for(i=0;i<n;i++){
printf("请依次输入第%d个物体的重量:",i+1) ;
scanf("%d",&w[i]);
}
sort(w,w+n); //调用sort函数将重量从小到大排序
for(i=0;i<n;i++){
if(sum+w[i]<=C){ //如果能装载第i件物品,装载之
sum=sum+w[i];
ans[i]='Y';
num++;
}
else{
ans[i]='N';
}
}
for(i=0;i<n;i++){
printf("%c ",ans[i]); //按照输入物体的顺序输出Y或N
}
printf("\n");
printf("所选中的物体的个数为%d,总重量为%d\n",num,sum);
return 0;
}
```