部分背包问题

在限定条件下，如何从众多物品中选出收益最高的几件物品，这样的问题就称为背包问题。

图 1 背包问题

举个简单的例子，商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品，选择哪些商品才能获得最大的收益呢？这个问题就属于背包问题，限定条件是背包的承重，最终目标是令背包中存放的物品的总收益最高。

根据不同的限定条件，背包问题还可以有更细致的划分：

0-1 背包问题：每件物品都不可再分，要么整个装入背包，要么放弃，不允许出现类似“将物品的 1/3 装入背包”的情况；

部分背包问题：每件物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包；

完全背包问题：挑选物品时，每件物品可以选择多个，也就是说不限物品的数量。

多重背包问题：每件物品的数量是有严格规定的，比如物品 A 有 2 件，物品 B 有 3 件。

不同的背包问题，对应的解决方案也不相同。本节我们给大家讲解，如何用贪心算法解决部分背包问题。

贪心算法解决部分背包问题

假设商店中有 3 种商品，它们各自的重量和收益是：

商品 1：重量 10 斤，收益 60 元；

商品 2：重量 20 斤，收益 100 元；

商品 3：重量 30 斤，收益 120 元。

对于每件商品，顾客可以购买商品的一部分（可再分）。一个小偷想到商店行窃，他的背包最多只能装 50 斤的商品，如何选择才能获得最大的收益呢？

贪心算法解决此问题的思路是：计算每个商品的收益率（收益/重量），优先选择收益率最大的商品，直至所选商品的总重量达到 50 斤。

如下是使用贪心算法解决此问题的伪代码：

// w 存储各个商品的重量，p 存储各个商品的收益，W 表示背包的承重 fractional_knapsack(w[] , p[] ,
W):
sort(w , p) //根据收益率对商品进行排序
i <- 0
while W > 0: //只要背包还有剩余空间，就一直装
temp = min(W , w[i]) //判断该商品能否全部装入
result[i] <- temp/w[i] //将实际装入到背包中的商品量以百分比的方式存储起来
W <- W - temp //计算背包的剩余容量，为装后续商品做准备
i <- i + 1
return result //返回统计装入信息的 result

如下是根据伪代码编写的 C 语言程序：

#include <stdio.h>
#define N 3    //设定商品数量
//根据收益率，对记录的商品进行从大到小排序
void Sort(float w[], float p[]) {
    int i,j;
    float temp;
    float v[N] = { 0 };
    //用v[]存商品的收益率
    for (i = 0; i < N; i++)
        v[i] = p[i] / w[i];
    //根据 v 数组记录的各个商品收益率的大小，同时对 w 和 p 数组进行排序
    for (i = 0; i < N; i++) {
        for (j = i + 1; j < N; j++) {
            if (v[i] < v[j]) {
                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;
    //根据收益率，重新商品进行排序
    Sort(w, p);
    //从收益率最高的商品开始装入背包，直至背包装满为止
    while (W > 0) {
        temp = W > w[i] ? w[i] : W;
        result[i] = temp / w[i];
        W -= temp;
        i++;
    }
}
int main() {
    int i;
    //统计背包中商品的总收益
    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 (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("最终收获的商品价值为 %.2f\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) {
        //根据收益率，重新对商品进行排序
        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
    #根据收益率，重新对商品进行排序
    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

当背包最大承重为 50 斤时，商品一全部装入，商品二也全部装入，商品三装入 2/3，此时收益是最大的。