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

故事描述

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

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

问题分析

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

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

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

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

算法设计

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

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

图解

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

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

(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。
  如想了解更多算法知识，可通过下方链接了解。