14《算法入门教程》贪心算法之背包问题

1.

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

2. 什么是背包问题？

假定咱们一共有 n 种物品，每一种物品 i 的价值为 vi，重量为 wi，咱们有一个背包，背包的容量为 c（至多可以放的物品重量不能超过 c），咱们需要选择物品放入背包中，使得背包当选择的物品中总价值最大，在这里每一个物品可以只选择部份。这便是咱们常说的背包问题文章源自微观生活（93wg.com）微观生活-https://93wg.com/5738.html

背包问题是一种常见的可以用贪心算法进行求解的问题，接下来，就让咱们看看怎么应用贪心算法解决背包问题。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5738.html

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

首先，这里咱们斟酌背包的容量为 30，并给出这个问题中咱们斟酌到的各类物品及对应的重量以及价值，如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5738.html

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

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

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

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

背包问题求解详解：

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

unitValue = 20/10 = 2
unitValue = 30/5 = 6
unitValue = 15/15 = 1
unitValue = 25/10 = 2.5
unitValue = 10/20 = 0.5
代码块12345

所以咱们有：

unitValue > unitValue > unitValue > unitValue > unitValue


当斟酌背包的容量为 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{
this.type = type;
this.weight = weight;
}

public Item{
this.type = type;
this.weight = weight;
this.value = value;
this.unitValue = value/weight;
}

@Override
public int compareTo {
return Double.valueOf.compareTo;
}
}

public static void main{
//背包容量
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{
Item item = new Item;
itemList.add;
}
//物品依照单价降序排序
Collections.sort;

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

//选择结果输出
for {
System.out.println;
}

}
}


运行结果如下：

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


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

5. 小结

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

以上就是微观生活（93wg.com）关于“14《算法入门教程》贪心算法之背包问题”的详细内容，希望对大家有所帮助！