减小
增大
默认

护眼
夜间
默认

部分背包问题

上一节
背包问题指的是在背包所能承受的重量范围内，将哪些物品装入背包可以获得最大的收益？


图 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 - temp
        i = i + 1

fractional_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

上一节