算法读书笔记-4

柔光的暖阳◎ 2023-09-24 13:52 40阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

## 阿里巴巴与四十大盗——背包问题 ##

### 故事描述 ###

有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着向上空飞扬，朝他这儿卷过来，而且越来越近。阿里巴巴心里害怕，担心碰到的是一伙儿强盗，他赶紧把毛驴赶到丛林的小道里，自己爬到一棵大树上躲了起来，这棵大树生长在一个大石头旁边。靠近以后，他才看清原来是一支马队，他们共有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋，他从丛林中来到那个大石头跟前，喃喃地说道：“芝麻，开门吧！”随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴躲在树上观察他们，直到他们走得无影无踪之后，才从树上下来。他大声喊道：“芝麻，开门吧！”他的喊声刚落，洞门立刻打开了。他小心翼翼地走了进去，一下子惊呆了，洞中堆满了财物，还有多得无法计数的金银珠宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金银财宝，阿里巴巴深信这肯定是强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用毛驴运走价值最大的财宝分给乡亲们呢？

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

### 问题分析 ###

本题为可分割背包问题，可以尝试贪心策略。

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

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

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

### 算法设计 ###

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

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

### 图解 ###

物品的价值和重量如下表所示。如果背包容量W=30，怎么才能装入最大价值的物品？  
![在这里插入图片描述][59b8dbe6f3644a2885429c05c61a0963.png]  
（1）贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行序排列，排序后的物品清单如下表所示。  
![在这里插入图片描述][fe8a5ba05f74443b89f8a3a1f72d80da.png]  
(2）按照贪心策略，每次选择单位重量价值大的物品装入背包。

*  第1次选择2号物品，剩余容量为30-2-28，当前已装入物品的最大价值为8。
 *  第2次选择10号物品，剩余容量为28-5-23，当前已装入物品的最大价值为8+15-23。
 *  第3次选择6号物品，剩余容量为23-8=15，当前已装入物品的最大价值为23+20-43。
 *  第4次选择3号物品，剩余容量为15-9=6，当前已装入物品的最大价值为43+18=61。
 *  第5次选择5号物品，剩余容量为6-5=1，当前已装入物品的最大价值为61+8=69。
 *  第6次选择8号物品，此时剩余容量为1，而8号物品的重量为4，无法全部装入，8号物品的单位重量价值为1.5，因此装入价值1×1.5=1.5，此时已装入物品的最大价值为69+1.5=70.5，剩余容量为0，背包己装满。  
    (3）构造最优解。  
    把这些已装入物品的序号组合在一起，即可得到最优解（2，10，6，3，5，8），其中最后一个物品为部分装入（8号物品装了1/4），已装入物品的最大价值为70.5。  
    如想了解更多算法知识，可通过下方链接了解。  
    [14天阅读挑战赛][14]

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[59b8dbe6f3644a2885429c05c61a0963.png]: https://img-blog.csdnimg.cn/59b8dbe6f3644a2885429c05c61a0963.png
[fe8a5ba05f74443b89f8a3a1f72d80da.png]: https://img-blog.csdnimg.cn/fe8a5ba05f74443b89f8a3a1f72d80da.png