433-贪心算法编程实战-蒲公英云

贪心算法思想

在这里插入图片描述
贪心算法：符合每一步的最优解，但是不一定是原问题的最优解

硬币问题

1,3,5分的硬币，现在给定一个价值c：11，问组成价值c需要的最少的硬币的数量？？？
贪心算法，就是一直优先选大的面值的硬币。
刚开始一直选5分硬币，选不了5分的硬币了，就选3分的，3分的硬币也选不了了，就选1分的硬币。

#include <iostream>
#include <algorithm>//泛型算法的头文件
using namespace std;
int main()
{
    int arr[] = {
     1,3,5 };
    int length = sizeof(arr) / sizeof(arr[0]);
    int c = 11;
    sort(arr, arr + length, [](int a, int b)->bool {
    return a > b; });//降序排序 
    int idx = 0;// 5 3 1
    int cnt = 0;//记录硬币的个数
    while (c > 0) 
    {
        if (c >= arr[idx])
        {
            c -= arr[idx];
            cnt++;//硬币数加1
        }
        else 
        {
            idx++;//数组下标往后走
        }
    }
    cout << cnt << endl;
    return 0;
}

运行截图如下
在这里插入图片描述

部分背包问题

部分背包问题
有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。
也就是说，每一个物体都可以只取走一部分，价值和重量按比例计算。求最大总价值。
也就是说，贪心算法可以一定要把c占满，优先把价值高的往里放。

贪心算法 -解决01背包 - 不一定得到最优解，因为在0-1背包，物品只存在放与不放，不能只放一个物品的其中的一部分，所以最后不一定把背包的容量占满

#include <iostream>
#include <algorithm>
using namespace std;
//描述物品的类
struct Product
{
    double getPrice()const//获取性价比 
    {
        return v * 1.0 / w;
    }
    bool operator>(const Product& p) const//重载大于> 
    {
        return getPrice() > p.getPrice();
    }
    int id;//物品的id
    int w;//物品的重量
    int v;//物品的价值
};
int main()
{
    int w[] = {
     8,6,4,2,5 };
    int v[] = {
     6,4,7,8,6 };
    const int n = sizeof(w) / sizeof(w[0]);//物品的个数
    int c = 12;
    int x[n] = {
     0 };//初始都给个0，有使用的置为1 
    Product pros[n];
    for (int i = 0; i < n; ++i)//初始化 
    {
        pros[i].id = i;
        pros[i].w = w[i];
        pros[i].v = v[i];
    }
    //按物品的性价比降序排列
    sort(pros, pros + n, [](const Product& p1, const Product& p2)->bool {
    return p1 > p2; });
    //按性价比高的往背包里面放（只考虑局部的最优解）
    double bestv = 0.0;//记录背包的最大价值
    for (int i = 0; i < n; ++i)
    {
        if (pros[i].w <= c)
        {
     //说明第i个物品可以装入背包
            bestv += pros[i].v;
            c -= pros[i].w;
        }
        else
        {
     //说明第i个物品无法全部装入背包，按剩余容量的比例装入物品的一部分
            bestv = bestv + pros[i].v * (c * 1.0 / pros[i].w);
            x[pros[i].id] = 1;
            break;//说明已经装完了！！！
        }
        x[pros[i].id] = 1;
    }
    cout << "bestv:" << bestv << endl;
    for (int v : x)
    {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}

运行截图如下
在这里插入图片描述

柜台提供服务问题

m个柜台提供服务，每个柜台给一个用户提供服务的时间是t(用数组表示每一个柜台提供服务的时间)，
问怎么排列，使得柜台给所有用户提供服务的时间最少？

贪心算法就是优先给给用户提供服务的时间的最少的柜台分配用户，然后再试着给其他的花费比较少时间的柜台分配用户

#include <iostream>
#include <algorithm>
using namespace std;
//定义柜台类 
struct Counter 
{
      //描述柜台
    bool operator<(const Counter &counter) const//重载< 
    {
        return time < counter.time;
    }
    int id;//柜台id
    int time;//柜台提供服务所花费的时间
};
int main()
{
    int arr[] = {
     3,2,4 };//每一个柜台处理每个用户所服务的时间
    const int m = sizeof(arr) / sizeof(arr[0]);//柜台的数量 3
    int n = 15;//办理业务的用户人数
    //定义柜台信息数组，初始化柜台id和time
    Counter cons[m];
    for (int i = 0; i < m; ++i) 
    {
        cons[i].id = i;
        cons[i].time = arr[i];
    }
    //按照柜台提供服务的时间升序排列
    sort(cons, cons + m);//从小到大排序
    int mintime = 0;//记录给所有用户提供服务的最少时间
    int x[m] = {
     0 };//记录每一个柜台安排的用户数量
    for (int i = 0; i < n; ++i)//遍历所有的用户 
    {
        //先计算把i用户放在0号柜台的时间，因为0号柜台提供服务的时间最快 
        int time = cons[0].time * (x[0] + 1);//0号柜台的i用户之前的人在x[0]放着，不着急给x[0]++，我们只是假设先放在0号柜台
        //因为不一定放在0柜台，有可能0号柜台人很多了，放在其他柜台效率还高呢
        //再遍历其它的柜台，看是否可以得到更少的花费时间
        int j = 1;
        for (; j < m; ++j) 
        {
            int t = cons[j].time * (x[j] + 1);
            if (t <= time) 
            {
       //放在其它柜台处理时间总体更快，直接放入j柜台
                x[j]++;
                //新添加了一个人，整体花费的时间有可能变得更长了，更新mintime
                if (t > mintime) 
                {
                    mintime = t;
                }
                break;
            }
        }
        //最终还是放在0号柜台花费时间最少
        if (j == m) 
        {
            x[0]++;
            //新添加了一个人，整体花费的时间有可能变得更长了，更新mintime
            mintime = cons[0].time * x[0];
        }
    }
    cout << mintime << endl;
    for (int i = 0; i < m; ++i) 
    {
        cout << arr[cons[i].id] << " : " << x[i] << endl;
    }
    return 0;
}