乐趣区

关于程序员:什么是背包问题

jiezi

本文首发自「慕课网」，想理解更多 IT 干货内容，程序员圈内热闻，欢送关注！

作者 | 慕课网精英讲师 JdreamZhang

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

背包问题是一种常见的能够用贪婪算法进行求解的问题，接下来，就让咱们看看如何利用贪婪算法解决背包问题。

  1. 贪婪算法求解背包问题
    首先，这里咱们思考背包的容量为 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
代码块 12345
所以咱们有：

unitValue(2) > unitValue(4) > unitValue(1) > unitValue(3) > unitValue(5)
代码块 1
当思考背包的容量为 30 时，咱们发现能够依照物品的单位价值进行顺次放入，直至背包容量放满或者物品放完为止，放入的过程如下：

依照如上步骤咱们简略剖析了一下背包问题的求解过程，接下来，咱们看一下如何用代码实现背包问题。

2.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);
    }

}

}
代码块 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
运行后果如下：

抉择了类型：2 的物品，分量为：5.0
抉择了类型：4 的物品，分量为：10.0
抉择了类型：1 的物品，分量为：10.0
抉择了类型：3 的物品，分量为：5.0
代码块 1234
代码中第 10 行至第 31 行定义了物品的一个外部类，用来存储一个物品的类型、分量、价值、单位分量的价值，并且实现在其中实现了一个比照函数。代码的第 35 至 42 行对应着开始的背包问题的初始化工作，别离初始化了背包容量、物品类型、物品分量、物品价值。代码的第 44 行至 51 即将所有物品依照物品外部类的格局退出数组，并且依照物品单位分量的价值进行降序排序。代码的第 53 行至第 66 行，依照背包问题的贪婪抉择办法抉择对应的物品，并记录抉择的物品类型及分量，放入到抉择的物品列表中，代码的 69 行 71 行输入相干的物品抉择后果。

3 小结
本篇文章次要利用了贪婪算法解决背包问题，须要大家把握贪婪算法解决背包问题的流程，并且能够本人用代码实现背包问题的求解。在学习完这篇文章后，咱们通过背包问题这一实例介绍了贪婪算法的理论利用，置信肯定能够帮忙大家更好的了解贪婪算法。

欢送关注「慕课网」，发现更多 IT 圈优质内容，分享干货常识，帮忙你成为更好的程序员！

退出移动版