贪心算法装载问题c语言
时间: 2023-11-20 15:55:46 浏览: 113
根据提供的引用,以下是使用贪心算法解决装载问题的C++代码:
```c++
#include <cstdio>
#include <algorithm>
using namespace std;
const int a=1005;
int n,C; //n个物体,最大载重量为C
int w[a]; //第i个物体的重量
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];
num++;
}
}
printf("最多可以装载%d个物体",num);
return 0;
}
```
该算法的思路是每次选择当前能够装载的最重的物品,直到无法再装载为止。具体实现中,我们首先将物品按照重量从小到大排序,然后依次选择能够装载的最重的物品,直到无法再装载为止。
相关问题
贪心算法装载问题C语言
这是一个经典的贪心算法问题,也称为背包问题。其思路是先将所有物体按重量从小到大排序,然后依次选择重量较小的物体,直到所选物体的总重量超过所允许的最大重量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;
}
```
贪心算法最优装载问题c语言
贪心算法最优装载问题是指有一批集装箱需要装载到船上,每个集装箱的重量不同且船的载重量有限,需要确定如何装载才能使船的装载重量最大。贪心算法最优装载问题的解决思路是每次选择当前剩余载重量中可以装载的最重集装箱装载到船上,直到无法再装载为止。
以下是贪心算法最优装载问题的C语言代码实现:
```c
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a, const void *b) { // qsort排序需要使用的比较函数
return *(int *)b - *(int *)a;
}
int main() {
int n, c; // 集装箱数量n和船的载重量c
scanf("%d%d", &n, &c);
int w[n];
for(int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
qsort(w, n, sizeof(int), cmp); // 将集装箱按重量从大到小排序
int ans = 0, sum = 0;
for(int i = 0; i < n; i++) {
if(sum + w[i] <= c) { // 如果当前集装箱可以装载到船上
ans++; // 船上集装箱数量+1
sum += w[i]; // 船上已装载集装箱重量增加
} else {
break;
}
}
printf("%d\n", ans); // 输出最多可装载集装箱数量
return 0;
}
```
阅读全文