贪心算法
贪心算法基本思路
image.png
贪心算法的基本思想
•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。
贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。
–动态规划：每个阶段产生的都是全局最优解
•第i阶段的“全局”： 问题空间为(a1, … , ai)
•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解
–贪心：每个阶段产生的都是局部最优解
•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai
•第i阶段的“局部最优解”： ai
贪心算法的基本要素
•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。
–这是贪心算法与动态规划算法的主要区别。
•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。
最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征
0-1背包——贪心算法
image-20210408193859442.png
image.png
image.png
// 贪心算法——0-1背包.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Item
{
int id;
float value;
float weight;
float v_w;
};
const int maxn = 1000;
bool isChosen[maxn];
vector<Item>item;
bool cmp(Item a,Item b)
{
if (a.v_w > b.v_w)
return true;
else
return false;
}
void Knapsack_greedy(int n,int M)
{
int totw = 0;//记录当前重量
for (int i = 0;i < n;i++)
{
if (totw + item[i].weight<=M)
{
isChosen[item[i].id] = true;
totw += item[i].weight;
}
}
}
int main()
{
int n;//物品数量
int M;//背包最大容量
cin >> n >> M;
float value, weight;
for (int i = 0;i < n;i++)
{
cin >> value >> weight;
item.push_back({ i,value,weight,value / weight });//存储物品信息
}
sort(item.begin(), item.end(), cmp);
Knapsack_greedy(n, M);
for (int i = 0;i < n;i++)
{
if (isChosen[i])
{
cout <<"选择物品为："<< i+1 << " ";
}
}
return 0;
}
