貪心算法之背包問題

1. 前言

本節(jié)內(nèi)容是貪心算法系列之一：背包問題，主要講解了什么是背包問題，如何利用貪心算法解決背包問題，給出了背包問題的實(shí)現(xiàn)偽代碼并進(jìn)行分析，并用 java 語言進(jìn)行了偽代碼實(shí)現(xiàn)，幫助大家通過背包問題更好的理解貪心算法思想的應(yīng)用。

2. 什么是背包問題？

假設(shè)我們一共有 n 種物品，每種物品 i 的價(jià)值為 vi，重量為 wi，我們有一個(gè)背包，背包的容量為 c（最多可以放的物品重量不能超過 c），我們需要選擇物品放入背包中，使得背包中選擇的物品中總價(jià)值最大，在這里每個(gè)物品可以只選擇部分。這便是我們常說的背包問題

背包問題是一種常見的可以用貪心算法進(jìn)行求解的問題，接下來，就讓我們看看如何利用貪心算法解決背包問題。

3. 貪心算法求解背包問題

首先，這里我們考慮背包的容量為 30，并給出這個(gè)問題中我們考慮到的各類物品及對(duì)應(yīng)的重量和價(jià)值，如下：

回顧一下我們?cè)谪澬乃惴ń榻B中提到的，能夠應(yīng)用貪心算法求解的問題需要滿足兩個(gè)條件：最優(yōu)子結(jié)構(gòu)和貪心選擇，接下來，我們就具體來看看在背包問題中的最優(yōu)子結(jié)構(gòu)和貪心選擇分別是什么。

首先，如果一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解，則此問題具備最優(yōu)子結(jié)構(gòu)的性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題是否可以用貪心算法求解的關(guān)鍵所在。對(duì)于背包問題，很顯然它是滿足最優(yōu)子結(jié)構(gòu)性質(zhì)的，因?yàn)橐粋€(gè)容量為 c 的背包問題必然包含容量小于 c 的背包問題的最優(yōu)解的。

其次，我們需要考慮在背包問題中，我們應(yīng)該按照什么樣的貪心選擇進(jìn)行選取。很顯然，如果要使得最終的價(jià)值最大，那么必定需要使得選擇的單位重量的物品的價(jià)值最大。所以背包問題的貪心選擇策略是：優(yōu)先選擇單位重量?jī)r(jià)值最大的物品，當(dāng)這個(gè)物品選擇完之后，繼續(xù)選擇其他價(jià)值最大的物品。

這里的背包問題可以用貪心算法實(shí)現(xiàn)，是因?yàn)楸嘲x擇放入的物品可以進(jìn)行拆分，即并不需要放入整個(gè)物品，可以選擇放入部分物品，我們這樣的背包選擇問題為部分背包問題（可以只選擇物品的部分），與之對(duì)應(yīng)的另一種背包問題為 0-1 背包問題，這個(gè)時(shí)候整個(gè)物品不可以拆分，只可以選擇放入或者不放入，0-1 背包問題用貪心算法并不能求得準(zhǔn)確的解，需要用動(dòng)態(tài)規(guī)劃算法求解。

背包問題求解詳解：

在這里，我們按照優(yōu)先選擇單位重量?jī)r(jià)值最大的物品，所以第一步需要計(jì)算單位每個(gè)物品的單位價(jià)值，如下：

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)

當(dāng)考慮背包的容量為 30 時(shí)， 我們發(fā)現(xiàn)可以按照物品的單位價(jià)值進(jìn)行依次放入，直至背包容量放滿或者物品放完為止，放入的過程如下：

按照如上步驟我們簡(jiǎn)單分析了一下背包問題的求解過程，接下來，我們看一下如何用代碼實(shí)現(xiàn)背包問題。

4.JAVA 代碼實(shí)現(xiàn)

在說明求解背包問題的整個(gè)過程之后，接下來，我們看看如何用 java 代碼實(shí)現(xiàn)背包問題的求解。

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

public class Knapsack {

    /**
     * 物品內(nèi)部類
     */
    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;
        //物品類型初始化數(shù)組
        int[] itemType = {1,2,3,4,5};
        //物品重量初始化數(shù)組
        double[] itemWeight = {10,5,15,10,30};
        //物品價(jià)值初始化數(shù)組
        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);
        }
        //物品按照單價(jià)降序排序
        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;
            }
        }

        //選擇結(jié)果輸出
        for (Item item : selectItemList){
            System.out.println("選擇了類型："+ item.type+" 的物品，重量為："+item.weight);
        }

    }
}

運(yùn)行結(jié)果如下：

選擇了類型：2 的物品，重量為：5.0
選擇了類型：4 的物品，重量為：10.0
選擇了類型：1 的物品，重量為：10.0
選擇了類型：3 的物品，重量為：5.0

代碼中第 10 行至第 31 行定義了物品的一個(gè)內(nèi)部類，用來存儲(chǔ)一個(gè)物品的類型、重量、價(jià)值、單位重量的價(jià)值，并且實(shí)現(xiàn)在其中實(shí)現(xiàn)了一個(gè)對(duì)比函數(shù)。代碼的第 35 至 42 行對(duì)應(yīng)著開始的背包問題的初始化工作，分別初始化了背包容量、物品類型、物品重量、物品價(jià)值。代碼的第 44 行至 51 行將所有物品按照物品內(nèi)部類的格式加入數(shù)組，并且按照物品單位重量的價(jià)值進(jìn)行降序排序。代碼的第 53 行至第 66 行，按照背包問題的貪心選擇方法選擇對(duì)應(yīng)的物品，并記錄選擇的物品類型及重量，放入到選擇的物品列表中 ，代碼的 69 行 71 行輸出相關(guān)的物品選擇結(jié)果。

5. 小結(jié)

本節(jié)主要學(xué)習(xí)了利用貪心算法處理背包問題，學(xué)習(xí)本節(jié)課程掌握貪心算法解決背包問題的流程，并且可以自己用代碼實(shí)現(xiàn)背包問題的求解。在學(xué)習(xí)完本節(jié)課程之后，我們通過背包問題這一實(shí)例介紹了貪心算法的實(shí)際應(yīng)用，幫助大家可以更好的理解貪心算法。