用最简单的0-1背包问题（1-0 knapsack problem）来说明穷举法、贪心算法、启发式算法。
0-1背包问题简述：
一、穷举法有一个背包，背包能装的物品重量是有限的，只能装C kg的物品。
现在有N个物品，每个物品都有自己的重量w和价值v。
现在要你决策：选哪些物品装进背包，才能使得不超过背包容量情况下，装的物品价值最大？
穷举法是一种暴力求解方式。首先穷举所以可能的情况，也就是找到解空间，然后遍历解空间找到最好的方案。
通过穷举生成解空间（n个物品）：对每个物品要么选择（1），要么不选择（0）；生成一个长度为n的数组，数组的每个元素表示每个物品，元素的值为0或1，得到的每个数组就是一种可能的解；所有的数组放一起就是解空间。n个物品，解空间中有2^n种可能（每个物品要么选择要么不选择）。
算例：背包能装载的最大重量为100，商品数量4个，重量分别是：18,42,88,3，价值分别是：141,136,192,223
package com.wuxiaolong.algorithm.knapsackProblem;
import java.util.ArrayList;
import java.util.List;
public class KnapsackProblem {
public static void main(String[] args) {
// 启动
exhaustAlgorithm();
}
public static void exhaustAlgorithm(){
// 1.算例定义：背包限制重量100 有4个物品 每个物品的重量和价值
double knapsackLimit = 100;
int goodsNum = 4;
double[] weights = {18,42,88,3};
double[] values ={141,136,192,223};
// 2.根据商品数量生成解空间(递归+回溯)
List> solutionSpace = getSolutionSpace(goodsNum);
// 3.评价每个解
double maxVal = 0;
List solve = null;
for(int i=0; i curr = solutionSpace.get(i);
double w = 0;
double v = 0;
for(int j=0; j=maxVal){
maxVal = v;
solve = curr;
}
}
}
// 4.输出最优解
System.out.println("最大价值："+ maxVal + " 最优方案："+solve);
}
public static List> getSolutionSpace(int goodsNum){
List> result = new ArrayList<>();
List path = new ArrayList<>();
// 递归的层数 相当于每个物品就是一层for
Integer index = 1;
Integer length = goodsNum;
// 递归
dfs(result,path,length,index);
System.out.println("解空间元素个数: "+result.size());
System.out.println("解空间详情：");
result.forEach(System.out::println);
return result;
}
public static void dfs(List> result,List path, int length, int index){
// 终止条件
if(index>length){
// 获取一个解
result.add(new ArrayList<>(path));
return;
}
// 每个物品有两种选择方式 1：选 0：不选
for(int i=0; i<2; i++){
path.add(i);
dfs(result,path,length,index+1);
// 回溯
path.remove(index-1);
}
}
}
1.2.运行结果
上面的背包问题，通过穷举法我们找到了最优解；上面有4个商品时，解空间有24=16种可能。当商品数为50个时，解空间中需要验证的解就是250=1125899906842624种可能，假如一秒钟可以计算10亿次，需要1125899秒=312小时。这在时间生活生产中是不能接受的。可见穷举法求解时间随问题规模增长而呈爆炸式增长，这也是穷举法的最大问题。
1.3.总结穷举法的特点：
- 通过比较解空间中的所有解（可行的和不可行的），穷举法一定能找到问题的最优解。穷举法简单粗暴，结果还是最优。
- 在问题规模较小时，是一种比较好的解决问题的方式
- 当问题规模过大时，求解所消耗的资源是不能接受的，需要寻找其他方式解决问题。
贪心算法是将一个问题差分成多个子问题，找到每个子问题的最优解就找到了全局的最优解。比如需要分别从10个箱子中取一张钞票（假如每个箱子中都有各种面额的钞票），要求取得的钞票加起来总面额最高，这时就可以从每个箱子中取最大面额的钞票就会使整个金额最大。对于某些问题贪心是一种很好的方式，但是对于某些情况，贪心就不能满足要求。贪心是一种目光短浅的做法，因为它只关注当前的最优性，而对于最后总体会变成什么样子就不管不顾了。
2.1.代码实现使用上面相同的算例，用贪心算法编码：
算例：背包能装载的最大重量为100，商品数量4个，重量分别是：18,42,88,3，价值分别是：141,136,192,223
package com.wuxiaolong.algorithm.knapsackProblem;
import java.util.*;
public class KnapsackProblem1 {
public static void main(String[] args) {
greedyAlgorithm();
}
public static void greedyAlgorithm(){
// 1.算例定义：背包限制 10个物品 每个物品的重量和价值
double knapsackLimt = 100;
int goodsNum = 4;
double[] weights = {18,42,88,3};
double[] values ={141,136,192,223};
// 2.商品信息放入item对象
List- goodsList = new ArrayList<>();
for(int i=0; i
(){
@Override
public int compare(Item o1, Item o2) {
return o2.getValWghtRate().compareTo(o1.getValWghtRate());
}
});
System.out.println("按照价值重量比排序后的结果：{}"+goodsList);
// 4.每次找满足条件的最大的商品，每个商品找一次
List- selectedGoods = new ArrayList<>();
double currSumWeight = 0;
double maxVal = 0;
for(int i=0; i
