贪心算法之背包问题

1. 前言

本节内容是贪心算法系列之一：背包问题，主要讲解了什么是背包问题，如何利用贪心算法解决背包问题，给出了背包问题的实现伪代码并进行分析，并用 java 语言进行了伪代码实现，帮助大家通过背包问题更好的理解贪心算法思想的应用。

2. 什么是背包问题？

假设我们一共有 n 种物品，每种物品 i 的价值为 vi，重量为 wi，我们有一个背包，背包的容量为 c（最多可以放的物品重量不能超过 c），我们需要选择物品放入背包中，使得背包中选择的物品中总价值最大，在这里每个物品可以只选择部分。这便是我们常说的背包问题

背包问题是一种常见的可以用贪心算法进行求解的问题，接下来，就让我们看看如何利用贪心算法解决背包问题。

3. 贪心算法求解背包问题

首先，这里我们考虑背包的容量为 30，并给出这个问题中我们考虑到的各类物品及对应的重量和价值，如下：

回顾一下我们在贪心算法介绍中提到的，能够应用贪心算法求解的问题需要满足两个条件：最优子结构和贪心选择，接下来，我们就具体来看看在背包问题中的最优子结构和贪心选择分别是什么。

首先，如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所在。对于背包问题，很显然它是满足最优子结构性质的，因为一个容量为 c 的背包问题必然包含容量小于 c 的背包问题的最优解的。

其次，我们需要考虑在背包问题中，我们应该按照什么样的贪心选择进行选取。很显然，如果要使得最终的价值最大，那么必定需要使得选择的单位重量的物品的价值最大。所以背包问题的贪心选择策略是：优先选择单位重量价值最大的物品，当这个物品选择完之后，继续选择其他价值最大的物品。

这里的背包问题可以用贪心算法实现，是因为背包选择放入的物品可以进行拆分，即并不需要放入整个物品，可以选择放入部分物品，我们这样的背包选择问题为部分背包问题（可以只选择物品的部分），与之对应的另一种背包问题为 0-1 背包问题，这个时候整个物品不可以拆分，只可以选择放入或者不放入，0-1 背包问题用贪心算法并不能求得准确的解，需要用动态规划算法求解。

背包问题求解详解：

在这里，我们按照优先选择单位重量价值最大的物品，所以第一步需要计算单位每个物品的单位价值，如下：

unitValue(1) = 20/10 = 2
unitValue(2) = 30/5  = 6
unitValue(3) = 15/15 = 1
unitValue(4) = 25/10 = 2.5
unitValue(5) = 10/20 = 0.5

所以我们有：

unitValue(2) > unitValue(4) > unitValue(1) > unitValue(3) > unitValue(5)

当考虑背包的容量为 30 时， 我们发现可以按照物品的单位价值进行依次放入，直至背包容量放满或者物品放完为止，放入的过程如下：

按照如上步骤我们简单分析了一下背包问题的求解过程，接下来，我们看一下如何用代码实现背包问题。

4.JAVA 代码实现

在说明求解背包问题的整个过程之后，接下来，我们看看如何用 java 代码实现背包问题的求解。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Knapsack {

    /**
     * 物品内部类
     */
    private static class Item implements Comparable<Item>{
        int type;
        double weight;
        double value;
        double unitValue;

        public Item(int type, double weight){
            this.type = type;
            this.weight = weight;
        }

        public Item(int type, double weight,double value){
            this.type = type;
            this.weight = weight;
            this.value = value;
            this.unitValue = value/weight;
        }

        @Override
        public int compareTo(Item o) {
            return Double.valueOf(o.unitValue).compareTo(this.unitValue);
        }
    }

    public static void main(String[] args){
        //背包容量
        double capacity = 30;
        //物品类型初始化数组
        int[] itemType = {1,2,3,4,5};
        //物品重量初始化数组
        double[] itemWeight = {10,5,15,10,30};
        //物品价值初始化数组
        double[] itemValue = {20,30,15,25,10};

        //初始化物品
        List<Item> itemList = new ArrayList<>();
        for(int i=0;i<itemType.length;i++){
            Item item = new Item(itemType[i],itemWeight[i],itemValue[i]);
            itemList.add(item);
        }
        //物品按照单价降序排序
        Collections.sort(itemList);

        //背包选择
        List<Item> selectItemList = new ArrayList<>();
        double selectCapacity = 0;
        for(Item item : itemList){
            if( (selectCapacity + item.weight) <= capacity){
                selectCapacity = selectCapacity + item.weight;
                Item selectItem = new Item(item.type,item.weight);
                selectItemList.add(selectItem);
            }else {
                Item selectItem = new Item(item.type, capacity-selectCapacity);
                selectItemList.add(selectItem);
                break;
            }
        }

        //选择结果输出
        for (Item item : selectItemList){
            System.out.println("选择了类型："+ item.type+" 的物品，重量为："+item.weight);
        }

    }
}

运行结果如下：

选择了类型：2 的物品，重量为：5.0
选择了类型：4 的物品，重量为：10.0
选择了类型：1 的物品，重量为：10.0
选择了类型：3 的物品，重量为：5.0

代码中第 10 行至第 31 行定义了物品的一个内部类，用来存储一个物品的类型、重量、价值、单位重量的价值，并且实现在其中实现了一个对比函数。代码的第 35 至 42 行对应着开始的背包问题的初始化工作，分别初始化了背包容量、物品类型、物品重量、物品价值。代码的第 44 行至 51 行将所有物品按照物品内部类的格式加入数组，并且按照物品单位重量的价值进行降序排序。代码的第 53 行至第 66 行，按照背包问题的贪心选择方法选择对应的物品，并记录选择的物品类型及重量，放入到选择的物品列表中 ，代码的 69 行 71 行输出相关的物品选择结果。

5. 小结

本节主要学习了利用贪心算法处理背包问题，学习本节课程掌握贪心算法解决背包问题的流程，并且可以自己用代码实现背包问题的求解。在学习完本节课程之后，我们通过背包问题这一实例介绍了贪心算法的实际应用，帮助大家可以更好的理解贪心算法。