贪心背包问题 背包问题 有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 C++程序
时间: 2024-04-07 20:33:46 浏览: 26
Sure! 这是一个经典的背包问题,也被称为0/1背包问题。下面是一个使用C++的贪心算法实现的例子:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
struct Item {
int weight;
int value;
};
bool compare(Item a, Item b) {
double ratioA = (double)a.value / a.weight;
double ratioB = (double)b.value / b.weight;
return ratioA > ratioB;
}
double fractionalKnapsack(Item arr[], int n, int capacity) {
sort(arr, arr + n, compare);
double totalValue = 0.0;
for (int i = 0; i < n; i++) {
if (arr[i].weight <= capacity) {
totalValue += arr[i].value;
capacity -= arr[i].weight;
} else {
totalValue += (double)arr[i].value / arr[i].weight * capacity;
break;
}
}
return totalValue;
}
int main() {
int capacity = 150;
Item items[7] = {
{35, 10},
{30, 40},
{60, 30},
{50, 50},
{40, 35},
{10, 40},
{25, 30}
};
int n = sizeof(items) / sizeof(items[0]);
double maxValue = fractionalKnapsack(items, n, capacity);
cout << "Maximum value that can be obtained: " << maxValue << endl;
return 0;
}
```
这个程序中,我们定义了一个Item结构体,包含物品的重量和价值。我们使用`compare`函数来对物品进行排序,按照单位重量的价值从大到小排序。然后使用贪心策略,从价值最高的物品开始装入背包,直到背包装满或者物品全部装入。
在主函数中,我们定义了一个背包容量为150,并初始化了7个物品的重量和价值。通过调用`fractionalKnapsack`函数计算出最大的总价值,并输出结果。
希望这个例子能够帮助到你!如有任何问题,请随时提问。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)