世界名画陈列馆问题,用C++和贪心算法解决
时间: 2023-12-14 09:35:50 浏览: 51
世界名画陈列馆问题是一个典型的贪心算法问题。其实质是从若干个可选的画作中选择一定数量的画作,使得这些画作的总价值最大,且满足某些限制条件。
具体来说,假设有 $n$ 幅画作,每幅画作的价值为 $v_i$,重量为 $w_i$,而且每幅画作只能选择一次。现在给定一个容量为 $W$ 的背包,问如何选择画作,使得选出的画作的总价值最大。
贪心算法的核心思想是每次选择当前最优的解,即选择单位重量价值最高的画作。具体实现时可以将画作按照单位重量价值降序排序,然后依次加入背包中,直到背包容量达到上限或者所有画作都已经加入。
以下是C++代码实现:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
struct Painting {
int value;
int weight;
double val; // 单位重量价值
};
bool cmp(Painting a, Painting b) {
return a.val > b.val; // 按照单位重量价值降序排序
}
int main() {
int n, W;
cin >> n >> W;
Painting* paintings = new Painting[n];
for (int i = 0; i < n; i++) {
cin >> paintings[i].value >> paintings[i].weight;
paintings[i].val = (double)paintings[i].value / paintings[i].weight;
}
sort(paintings, paintings + n, cmp); // 排序
int total_value = 0;
for (int i = 0; i < n && W > 0; i++) {
if (paintings[i].weight <= W) { // 如果能够放下,则全部放入
total_value += paintings[i].value;
W -= paintings[i].weight;
}
else { // 否则计算部分放入的价值
total_value += W * paintings[i].val;
W = 0;
}
}
cout << "Total value: " << total_value << endl;
delete[] paintings;
return 0;
}
```
时间复杂度为 $O(n \log n)$,其中 $n$ 是画作的数量。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)