首页 > 编程笔记

部分背包问题

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


图 1 背包问题


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

根据不同的限定条件,背包问题还可以有更细致的划分:
不同的背包问题,对应的解决方案也不相同。本节我们给大家讲解,如何用贪心算法解决部分背包问题。

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

假设商店中有 3 种商品,它们各自的重量和收益是:
对于每件商品,顾客可以购买商品的一部分(可再分)。一个小偷想到商店行窃,他的背包最多只能装 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,此时收益是最大的。

推荐阅读