语言实现最优装载的贪心算法
时间: 2023-10-14 10:06:28 浏览: 44
最优装载问题是指给定一个容量为C的集装箱和n个物品,每个物品有一个重量w和一个价值v,现在要把这些物品装进集装箱中,使得总价值最大。每个物品只能选择装或不装,不能分割。
贪心算法思路:
1. 将物品按单位重量的价值v[i]/w[i]从大到小排序。
2. 依次将排序后的物品放入集装箱中,直到集装箱装满为止。
C++代码实现:
```c++
#include<bits/stdc++.h>
using namespace std;
struct Goods {
double w, v;
double unitV;
};
bool cmp(Goods a, Goods b) {
return a.unitV > b.unitV;
}
double MaxValue(Goods goods[], int n, double C) {
sort(goods, goods + n, cmp); //按单位价值从大到小排序
double res = 0.0;
for (int i = 0; i < n && C > 0; i++) {
if (C >= goods[i].w) { //当前物品可以全部装进集装箱
res += goods[i].v;
C -= goods[i].w;
}
else { //当前物品只能部分装进集装箱
res += goods[i].unitV * C;
C = 0;
}
}
return res;
}
int main() {
int n;
double C;
cin >> n >> C;
Goods goods[n];
for (int i = 0; i < n; i++) {
cin >> goods[i].w >> goods[i].v;
goods[i].unitV = goods[i].v / goods[i].w; //计算单位价值
}
cout << MaxValue(goods, n, C) << endl;
return 0;
}
```
相关推荐
![text/x-c++](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)