某货轮的最大载重量为M,现有N件货物供选择装船,且每件货物的重量和价值均不同。要求从N件货物中挑选若干件上船,在满足货物总重量小于等于M的前提下,运输货物的总价值最大。◼分析:本题可以选择贪心算法,优先挑价钱高且重量轻的货物装船。对每件货物,计算其价值与重量之比,称之为"价重比",价重比高的货物优先装船,每装一件累计其重量,总重量不超过货轮的载重量M。
时间: 2024-03-08 16:49:24 浏览: 163
是的,您的分析是正确的。这是一道经典的背包问题,可以用贪心算法来解决。
具体的做法是,对于每个物品,计算其价值与重量之比,称之为“价重比”。然后按照“价重比”从大到小排序,依次选择“价重比”最大的物品装船,直到货物总重量达到或超过货轮的最大载重量M。
下面是一个示例代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Goods {
int weight; // 货物重量
int value; // 货物价值
double ratio; // 货物价重比
};
bool cmp(Goods a, Goods b) {
return a.ratio > b.ratio; // 按照价重比从大到小排序
}
int main() {
int M = 10; // 货轮最大载重量
vector<Goods> goods = {{2, 6}, {2, 3}, {6, 5}, {5, 4}, {4, 6}}; // 货物重量和价值
int n = goods.size();
for(int i = 0; i < n; i++) {
goods[i].ratio = (double) goods[i].value / goods[i].weight; // 计算价重比
}
sort(goods.begin(), goods.end(), cmp); // 按照价重比从大到小排序
int totalWeight = 0, totalValue = 0;
for(int i = 0; i < n; i++) {
if(totalWeight + goods[i].weight <= M) { // 如果货物总重量不超过货轮最大载重量M
totalWeight += goods[i].weight;
totalValue += goods[i].value;
} else { // 如果货物总重量超过货轮最大载重量M
int remaining = M - totalWeight; // 剩余容量
totalWeight += remaining;
totalValue += goods[i].ratio * remaining;
break;
}
}
cout << "Total weight: " << totalWeight << endl; // 输出实际装载的货物总重量
cout << "Total value: " << totalValue << endl; // 输出实际装载的货物总价值
return 0;
}
```
输出结果为:
```
Total weight: 10
Total value: 20
```
表示实际装载的货物总重量为10,总价值为20。
希望这个示例代码能够帮到您!
阅读全文