【趣学算法】Day3 贪心算法——背包问题
14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！
渲染
cocoa
云原生实战
❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️
stylegan3
🧑个人主页：@周小末天天开心
numpy
各位大佬的点赞👍 收藏⭐ 关注✅，是本人学习的最大动力
研究生
感谢！
mybatis配置
📕该篇文章收录专栏—趣学算法
scrum
目录
就业前景
编译
注册登录界面制作
plugin
图像分类
Java异常处理
机械
keil mdk
立体相机
线性表
MySQL Workbench
题目描述
有n种物品，每种物品只有一个，第i种物品的重量为 wi，价值为 vi，背包的容量为 w，物品可以分割。如何放置物品，使装入背包的物品价值之和最大?
hadoop数据排序
问题分析
（1）每次选择价值最大的物品装入背包。
TRS
（2）每次选择重量最小的物品装入背包。
Android
（3）每次选择单位重量价值最大的物品转入背包。
经验分享
思考一下，如果选价值最大的物品，但重量非常大，则可能一个也装不下，分割一部分装入，价值未必是最高的；如果选重量最小的物品装入，则其价值不一定高，所以在总重量受到限制的情况下无法保证价值最大；而如果每次选单位重量价值最大的物品，则装满背包后一定能得到最大价值。
ERC1155 协议详解
因此，我们应采用第三种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。
智能小车
算法设计
（1）确定合适的数据结构并初始化。首先将物品的重量、价值和单位重量价值定位为一种结构体类型，然后对物品按单位重量价值从大到小进行排序。
Linux面试题
（2）根据贪心策略，按照单位重量价值从大到小选取物品，直到达到背包容量。如果在装入第 i 个物品时超出背包容量，则取该物品的一部分装入背包。
自动控制原理
完美图解
物品的价值和重量如表2-3所示。如果背包容量 w = 30，怎么才能装入最大价值的物品？
ctp
物品清单
qt
| 物品 i3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 重量 w[i] | 4 | 2 | 9 | 5 | 5 | 8 | 5 | 4 | 5 | 5 |
| 价值 v[i] | 3 | 8 | 18 | 6 | 8 | 20 | 5 | 6 | 7 | 15 |
（1）贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行降序排列，排序后的物品清单如下所示：
python3
排序后的物品清单
| 物品 i | 2 | 10 | 6 | 3 | 5 | 8 | 9 | 4 | 7 | 1 |
| 重量 w[i] | 2 | 5 | 8 | 9 | 5 | 4 | 5 | 5 | 5 | 4 |
| 价值 v[i] | 8 | 15 | 20 | 18 | 8 | 6 | 7 | 6 | 5 | 3 |
| 单位重量价值 | 4 | 3 | 2.5 | 2 | 1.6 | 1.5 | 1.4 | 1.2 | 1 | 0.75 |
（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)。 
