贪心算法

贪心算法的基本思想

•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。

贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。

–动态规划：每个阶段产生的都是全局最优解

•第i阶段的“全局”： 问题空间为(a1, … , ai)

•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解

–贪心：每个阶段产生的都是局部最优解

•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai

•第i阶段的“局部最优解”： ai

贪心算法的基本要素

•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。

–这是贪心算法与动态规划算法的主要区别。

•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

最优装载——贪心算法

image.png

首先证明该问题具有贪心选择性质和最优子结构性质

1.最轻者先装一定是整体最优解，满足贪心选择

2.该问题的子问题仍是最优解，满足最优子结构

// 贪心算法---最优装载.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>


using namespace std;

const int maxn = 10;

int main()
{
    pair<int,int>w[maxn];//pair <物品编号，物品重量>
    int isLoad[maxn] = { 0 };//统计物品是否装载
    int capacity;//最大承载
    cin >> capacity;
    int num = 0;//统计数量
    int weight = 0;//统计当前重量
    for (int i = 0;i < maxn;i++)
    {
        w[i].first = i;
        cin >> w[i].second;
    }

    sort(w, w + 10);

    for (int i = 0;i < maxn&&weight<=capacity;i++)
    {
        isLoad[w[i].first] = 1;
        weight += w[i].second;
    }

    for (int i = 0;i < maxn;i++)
    {
        if (isLoad[i])
            cout << i << " ";
    }


    return 0;
}