close

(Greedy Search) C++ 中的 贪心搜索算法- 解释、示例和代码

贪心搜索算法是一种解决问题的方法，它总是在每一步中选择最佳的可用选项，而不考虑决策的长期影响。 虽然它不能保证找到全局最优解决方案，但这种方法通常效果很快并且易于实施。

怎么运行的

  1. 初始化： 从空的或初始的解决方案开始。
  2. 局部最优选择： 在每一步中，根据目标函数或定义的标准选择局部最优选择。
  3. 应用选择： 将最优选择应用于当前解决方案。
  4. 重复： 迭代步骤2到4，直到无法做出更好的局部选择。

例子： Knapsack Problem

考虑一下 Knapsack Problem，我们有一个具有最大重量的背包和一个具有重量和值的物品列表。 目标是选择物品以使背包中的总价值最大化。 解决此问题的贪婪搜索方法是根据最高的价值重量比来选择项目。

C++ 代码示例 

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
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 greedyKnapsack(int maxWeight, std::vector<Item>& items) {  
    double totalValue = 0.0;  
  
    std::sort(items.begin(), items.end(), compare);  
  
    for(const Item& item: items) {  
        if(maxWeight >= item.weight) {  
            totalValue += item.value;  
            maxWeight -= item.weight;  
        } else {  
            totalValue +=(double)maxWeight / item.weight * item.value;  
            break;  
        }  
    }  
  
    return totalValue;  
}  
  
int main() {  
    int maxWeight = 10;  
    std::vector<Item> items = {{2, 6}, {5, 12}, {3, 8}, {7, 14}, {4, 10}};  
    double maxValue = greedyKnapsack(maxWeight, items);  
  
    std::cout << "Max value in knapsack: " << maxValue << std::endl;  
  
    return 0;  
}

在这个例子中，我们使用贪心搜索方法来解决 Knapsack Problem. 我们根据价值与重量比率的降序对物品进行排序，并选择比率最高且仍符合背包重量限制的物品。