什么是背包问题？

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

作者| 慕课网精英讲师 JdreamZhang

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

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

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

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

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

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

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

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

背包问题求解详解：

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

unitValue(1) = 20/10 = 2unitValue(2) = 30/5 = 6unitValue(3) = 15/15 = 1unitValue(4) = 25/10 = 2.5unitValue(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{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;}@Overridepublic 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 itemList = new ArrayList();for(int i=0;i selectItemList = new ArrayList();double selectCapacity = 0;for(Item item : itemList){if( (selectCapacity + item.weight)