【趣学算法】Day3 贪心算法——背包问题

14天阅读挑战赛 努力是为了不平庸~ 算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！

 ❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️ 🧑个人主页：@周小末天天开心 各位大佬的点赞👍 收藏⭐ 关注✅，是本人学习的最大动力 感谢！ 📕该篇文章收录专栏—趣学算法

目录

题目描述

问题分析

算法设计 

完美图解

算法详解

（1）确定合适的数据结构。

（2）对物体按单位重量价值进行排序。

（3）使用贪心算法求解问题

算法分析

题目描述

        有n种物品，每种物品只有一个，第i种物品的重量为 wi，价值为 vi，背包的容量为 w，物品可以分割。如何放置物品，使装入背包的物品价值之和最大?

问题分析

（1）每次选择价值最大的物品装入背包。

（2）每次选择重量最小的物品装入背包。

（3）每次选择单位重量价值最大的物品转入背包。

        思考一下，如果选价值最大的物品，但重量非常大，则可能一个也装不下，分割一部分装入，价值未必是最高的；如果选重量最小的物品装入，则其价值不一定高，所以在总重量受到限制的情况下无法保证价值最大；而如果每次选单位重量价值最大的物品，则装满背包后一定能得到最大价值。

        因此，我们应采用第三种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。

算法设计 

（1）确定合适的数据结构并初始化。首先将物品的重量、价值和单位重量价值定位为一种结构体类型，然后对物品按单位重量价值从大到小进行排序。

（2）根据贪心策略，按照单位重量价值从大到小选取物品，直到达到背包容量。如果在装入第 i 个物品时超出背包容量，则取该物品的一部分装入背包。

完美图解

        物品的价值和重量如表2-3所示。如果背包容量 w = 30，怎么才能装入最大价值的物品？

                                                                物品清单

（1）贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行降序排列，排序后的物品清单如下所示：

                                                         排序后的物品清单

 （2）按照贪心策略，每次选择单位重量价值大的物品装入背包。

（3）构造最优解

算法详解

（1）确定合适的数据结构。

struct node {
    double w; //每种物品的重量
    double v; //每种物品的价值
    double p; //每种物品的单位重量价值（价值/重量）
}

（2）对物体按单位重量价值进行排序。

bool cmp(node a, node b) { //自定义比较函数cmp
    return a.p > b.p; // 指定按照物品的单位重量价值进行降序排列
}
sort(s, s + n, cmp); //前两个参数分别为待排序数组的首地址和尾地址，cmp为比较函数

（3）使用贪心算法求解问题

double solve (int n, double w) {
    double sum = 0.0;    //sum表示已经装入物品的价值之和
    double cleft = w;    //背包的剩余容量
    for(int i = 0; i < n; i++) {    //是用贪心算法求解问题
        if(s[i].w < cleft) {    //如果物品的重量小于或等于剩余容量
            cleft -= s[i].w;
            sum += s[i].v;
        }
        else {    //如果物品的重量大于剩余容量
            sum += cleft * s[i].p;    //部分装入
            break;
        }
    }
    return sum;
}

算法分析

（1）时间复杂度：时间主要耗费在对物品按单位重量价值进行排序上，一般采用快速排序法，时间复杂度为O(nlogn)。

（2）空间复杂度：空间主要消耗在存储物品的单位重量价值上，空间复杂度为O(n)。