背包问题指的是在背包所能承受的重量范围内,将哪些物品装入背包可以获得最大的收益?
图 1 背包问题
举个例子,一个小偷正在商店行窃,他随身携带的背包可以装一定重量的商品,商店中摆放着不同重量和价值的商品,小偷应该如何选择才能获得最大的收益?这样的问题就属于背包问题。
根据所选物品是否可再分(比如选择某物品的 1/2),背包问题可分为以下两种:
0-1 背包问题:挑选物品时,单个物品要么放弃,要么全部装入背包,不存在“装入 1/2 物品”的情况;
部分背包问题:挑选物品时,单个物品可再分,例如将物品的 1/2 装入背包。
本节给您讲解的是如何使用贪心算法解决部分背包问题。
部分背包问题的解决方案
接下来以“小偷在商店行窃,商店的商品都可再分”为例,给您讲解如何解决部分背包问题。
为了方便讲解,我们做以下假设:
背包最多可以承受的商品重量为 W(后续简称承重);
商店共有 n 件商品,它们都是可再分的,其中第 i 件商品的总重量为 Wi,总收益为 Pi。
显然,要想获得最大的收益,小偷需要做到以下 2 点:
充分利用背包的承重,背包装的商品越多,获得收益就越大;
确保选中的 W 重量商品中,单位重量下获得的收益最大。
结合以上 2 点,我们可以采用贪心算法来解决这个问题,具体的解决方案是:计算每个商品的收益率(即 Pi/Wi),优先选择收益率最大的商品,直至选择的商品总重量恰好为 W。
假设背包的承重为 20,商店**有 3 种商品,它们的重量和收益分别为:
商品 1:重量 10,收益 60,单位重量的收益为 6;
商品 2:重量 20,收益 100,单位重量的收益为 5;
商品 3:重量 30,收益 120,单位重量的收益为 4。
通过比较收益率,以上 3 种商品装入背包的顺序依次为:商品 1 > 商品 2 > 商品 3。受到背包承重的限制,商品 1 可以全部装入背包,而商品 2 只能装一半(10 斤),商品 3 无法被装入。
部分背包问题的具体实现
如下为采用贪心算法解决部分背包问题的伪代码:
// w 存储各个商品的重量,p 存储各个商品的收益,W 表示背包的承重
fractional_knapsack(w[] , p[] , W):
sort(w , p) //根据收益率对 w 和 p 中存储的商品进行排序
i <- 0
while W > 0: //从收益率最高的商品开始装
temp = min(W , w[i]) //判断该商品能否全部装入
result[i] <- temp / w[i] //将实际装入到背包中的商品量依次存储到 result 中
W <- w - temp //计算背包的剩余容量,为装后续商品做准备
i <- i + 1
end while
return result //返回统计装入信息的 result
注意,最终 result 记录的各个商品装入量的信息,对应的是根据收益率重新排序后的各个商品。
下面的 C 语言程序演示了贪心算法解决部分背包问题的整个过程:
#include <stdio.h>#define N 3 //设定商品数量//根据收益率,对记录的商品进行从大到小排序void Sort(float w[], float p[]) {float v[N] = { 0 };//用v[]存商品的收益率for (int i = 0; i < N; i++)v[i] = p[i] / w[i];//根据 v 数组记录的各个商品收益率的大小,同时对 w 和 p 数组进行排序for (int i = 0; i < N; i++) {for (int j = i + 1; j < N; j++) {if (v[i] < v[j]) {float temp = v[i];v[i] = v[j];v[j] = temp;temp = w[i];w[i] = w[j];w[j] = temp;temp = p[i];p[i] = p[j];p[j] = temp;}}}}/*贪心算法解决部分背包问题w:记录各个商品的总重量p:记录各个商品的总价值result:记录各个商品装入背包的比例W:背包的容量*/void fractional_knapsack(float w[], float p[], float result[], float W) {float temp = 0;int i = 0;//根据收益率,重新对 w 和 p 记录的商品信息进行排序Sort(w, p);//从收益率最高的商品开始装入背包,直至背包装满为止while (W > 0) {temp = W > w[i] ? w[i] : W;result[i] = temp / w[i];W -= temp;i++;}}int main() {//统计背包中商品的总收益float values = 0;//各个商品的重量float w[N] = { 10,30,20 };//各个商品的价值float p[N] = { 60,100,120 };float result[N] = {0};//调用解决部分背包问题的函数fractional_knapsack(w, p, result, 50);//根据 result 数组中记录的数据,决定装入哪些商品for (int i = 0; i < N; i++) {if (result[i] == 1) {printf("总重量为 %f,总价值为 %f 的商品全部拿走\n", w[i], p[i]);values += p[i];}else if (result[i] == 0)printf("总重量为 %f,总价值为 %f 的商品不拿走\n", w[i], p[i]);else {printf("总重量为 %f,总价值为 %f 的商品拿走 %f%%\n", w[i], p[i],result[i]*100);values += p[i] * result[i];}}printf("最终收获的商品价值为 %f\n",values);return 0;}
下面的 Java 程序演示了贪心算法解决部分背包问题的整个过程:
public class Demo {//根据收益率,对记录的商品进行从大到小排序public static void sort(float [] w, float [] p) {int length = w.length;//用v[]存商品的收益率float [] v = new float[length];for (int i=0;i<length;i++) {v[i] = p[i]/w[i];}//根据 v 数组记录的各个商品收益率的大小,同时对 w 和 p 数组进行排序for (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {if (v[i] < v[j]) {float temp = v[i];v[i] = v[j];v[j] = temp;temp = w[i];w[i] = w[j];w[j] = temp;temp = p[i];p[i] = p[j];p[j] = temp;}}}}/*贪心算法解决部分背包问题 w:记录各个商品的总重量 p:记录各个商品的总价值 result:记录各个商品装入背包的比例 W:背包的容量 */public static void fractional_knapsack(float []w, float []p, float []result, float W) {//根据收益率,重新对 w 和 p 记录的商品信息进行排序sort(w, p);int i=0;//从收益率最高的商品开始装入背包,直至背包装满为止while (W > 0) {float temp = W > w[i]?w[i]:W;result[i] = temp / w[i];W -= temp;i++;}}public static void main(String[] args) {//设定背包的容量float W = 50;//各个商品的重量float [] w = { 10,30,20 };//各个商品的价值float [] p = { 60,100,120 };//统计背包中商品的总收益float [] result = {0,0,0};//调用解决部分背包问题的函数fractional_knapsack(w,p,result,W);//统计背包中商品的总收益float values = 0;//根据 result 数组中记录的数据,决定装入哪些商品for (int i = 0; i < w.length; i++) {if (result[i] == 1) {System.out.println("总重量为"+w[i]+",总价值为"+p[i]+"的商品全部拿走");values += p[i];}else if (result[i] == 0)System.out.println("总重量为"+w[i]+",总价值为"+p[i]+"的商品不拿走");else {System.out.println("总重量为"+w[i]+",总价值为"+p[i]+"的商品拿走"+result[i]*100+"%");values += p[i] * result[i];}}System.out.print("最终收获的商品价值为"+values);}}
下面的 Python 程序演示了贪心算法解决部分背包问题的整个过程:
#设定背包的容量W = 50#各个商品的重量w = [10,30,20]#各个商品的价值p = [60,100,120]#根据收益率,对记录的商品进行从大到小排序def sort():#用v列表存商品的收益率v = []length = len(w)for i in range(length):v.append(p[i]/w[i])#根据 v 列表记录的各个商品收益率的大小,同时对 w 和 p 数组进行排序for i in range(length):for j in range(i+1,length):if v[i] < v[j]:v[i],v[j] = v[j],v[i]w[i],w[j] = w[j],w[i]p[i],p[j] = p[j],p[i]result = [0,0,0]def fractional_knapsack():global W#根据收益率,重新对 w 和 p 记录的商品信息进行排序sort()i = 0#从收益率最高的商品开始装入背包,直至背包装满为止while(W>0):temp = min(W,w[i])result[i] = temp/w[i]W = W - tempi = i + 1fractional_knapsack()#统计背包中商品的总收益values = 0#根据 result 列表中记录的数据,决定装入哪些商品for i in range(len(result)):if result[i] ==1:print("总重量为 %f,总价值为 %f 的商品全部拿走"%(w[i],p[i]))values = values + p[i]elif result[i]==0:print("总重量为 %f,总价值为 %f 的商品不拿走"%(w[i],p[i]))else:print("总重量为 %f,总价值为 %f 的商品拿走%f%%"%(w[i],p[i],result[i]*100))values = values + p[i]*result[i]print("最终收获的商品价值为:%f" %(values))
以上程序的执行结果均为:
总重量为 10.000000,总价值为 60.000000 的商品全部拿走
总重量为 20.000000,总价值为 120.000000 的商品全部拿走
总重量为 30.000000,总价值为 100.000000 的商品拿走66.666667%
最终收获的商品价值为:246.666667