通过0-1背包问题看穷举法、贪心算法、启发式算法（JAVA）

布满荆棘的人生 2022-09-16 04:54 182阅读 0赞

用最简单的0-1背包问题（1-0 knapsack problem）来说明穷举法、贪心算法、启发式算法。

0-1背包问题简述：

> 有一个背包，背包能装的物品重量是有限的，只能装C kg的物品。  
> 现在有N个物品，每个物品都有自己的重量w和价值v。  
> 现在要你决策：选哪些物品装进背包，才能使得不超过背包容量情况下，装的物品价值最大？

## 一、穷举法 ##

穷举法是一种暴力求解方式。首先穷举所以可能的情况，也就是找到解空间，然后遍历解空间找到最好的方案。  
通过穷举生成解空间（n个物品）：对每个物品要么选择（1），要么不选择（0）；生成一个长度为n的数组，数组的每个元素表示每个物品，元素的值为0或1，得到的每个数组就是一种可能的解；所有的数组放一起就是解空间。n个物品，解空间中有2^n种可能（每个物品要么选择要么不选择）。

### 1.1.代码实现 ###

算例：背包能装载的最大重量为100，商品数量4个，重量分别是：18,42,88,3，价值分别是：141,136,192,223

package com.wuxiaolong.algorithm.knapsackProblem;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * 整数规划中的 0-1背包问题 */
    public class KnapsackProblem { 
    
        public static void main(String[] args) { 
            // 启动
            exhaustAlgorithm();
        }
    
        /** * 1.穷举法 * */
        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<List<Integer>> solutionSpace = getSolutionSpace(goodsNum);
    
            // 3.评价每个解
            double maxVal = 0;
            List<Integer> solve = null;
            for(int i=0; i<solutionSpace.size();i++){ 
                List<Integer> curr = solutionSpace.get(i);
                double w = 0;
                double v = 0;
                for(int j=0; j<curr.size(); j++){ 
                    if(curr.get(j) == 1){ 
                        w += weights[j];
                        v += values[j];
                    }
                }
    
                // 满足约束条件
                if(w<=knapsackLimit){ 
                    if(v>=maxVal){ 
                        maxVal = v;
                        solve = curr;
                    }
                }
            }
    
            // 4.输出最优解
            System.out.println("最大价值："+ maxVal + " 最优方案："+solve);
        }
    
        /** * 穷举解空间中的所有解 */
        public static List<List<Integer>> getSolutionSpace(int goodsNum){ 
    
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> 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<List<Integer>> result,List<Integer> 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.运行结果 ###

![image-20211014175529798][]

上面的背包问题，通过穷举法我们找到了最优解；上面有4个商品时，解空间有24=16种可能。当商品数为50个时，解空间中需要验证的解就是250=1125899906842624种可能，假如一秒钟可以计算10亿次，需要1125899秒=312小时。这在时间生活生产中是不能接受的。可见穷举法求解时间随问题规模增长而呈爆炸式增长，这也是穷举法的最大问题。

### 1.3.总结 ###

穷举法的特点：

1.  通过比较解空间中的所有解（可行的和不可行的），穷举法一定能找到问题的最优解。穷举法简单粗暴，结果还是最优。
2.  在问题规模较小时，是一种比较好的解决问题的方式
3.  当问题规模过大时，求解所消耗的资源是不能接受的，需要寻找其他方式解决问题。

## 二、贪心算法 ##

贪心算法是将一个问题差分成多个子问题，找到每个子问题的最优解就找到了全局的最优解。比如需要分别从10个箱子中取一张钞票（假如每个箱子中都有各种面额的钞票），要求取得的钞票加起来总面额最高，这时就可以从每个箱子中取最大面额的钞票就会使整个金额最大。对于某些问题贪心是一种很好的方式，但是对于某些情况，贪心就不能满足要求。贪心是一种目光短浅的做法，因为它只关注当前的最优性，而对于最后总体会变成什么样子就不管不顾了。

### 2.1.代码实现 ###

使用上面相同的算例，用贪心算法编码：

算例：背包能装载的最大重量为100，商品数量4个，重量分别是：18,42,88,3，价值分别是：141,136,192,223

package com.wuxiaolong.algorithm.knapsackProblem;
    
    import java.util.*;
    
    /** * 整数规划中的 0-1背包问题 * */
    public class KnapsackProblem1 { 
    
        public static void main(String[] args) { 
            greedyAlgorithm();
        }
    
        /** * 1.贪心算法 * 每次拿满足条件的价值最大的商品，如果不满足条件就拿价值次大的商品，依次内推..... * */
        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<Item> goodsList = new ArrayList<>();
            for(int i=0; i<values.length; i++){ 
                Item item = new Item(weights[i],values[i],i);
                goodsList.add(item);
            }
    
            // 3.将商品列表按照价值重量比排序
            Collections.sort(goodsList, new Comparator<Item>(){ 
                @Override
                public int compare(Item o1, Item o2) { 
                    return o2.getValWghtRate().compareTo(o1.getValWghtRate());
                }
            });
            System.out.println("按照价值重量比排序后的结果：{}"+goodsList);
    
            // 4.每次找满足条件的最大的商品，每个商品找一次
            List<Item> selectedGoods = new ArrayList<>();
            double currSumWeight = 0;
            double maxVal = 0;
            for(int i=0; i<goodsList.size(); i++){ 
                Item tmp = goodsList.get(i);
    
                if(currSumWeight + tmp.getWeight() < knapsackLimt){ 
                    selectedGoods.add(tmp);
                    currSumWeight += tmp.getWeight();
                    tmp.setSelect(1);
                    maxVal += tmp.getValue();
                }
            }
    
            // 5.打印最优结果
            int[] solve = new int[goodsList.size()];
            for (Item t : selectedGoods){ 
                solve[t.getOrder()] = t.getSelect();
            }
            System.out.println("最大价值："+ maxVal + " 最优方案："+ Arrays.toString(solve));
        }
    
    
        public static class Item{ 
            // 重量
            private Double weight;
            // 价值
            private Double value;
            // 价值重量比
            private Double valWghtRate;
            // 商品原来的顺序
            private Integer order;
            // 是否选择该商品 默认不选
            private Integer select = 0;
    
            public Item(){ }
    
            public Item(Double weight,Double value,Integer order){ 
                this.weight = weight;
                this.value = value;
                this.order = order;
                this.valWghtRate = value/weight;
            }
    
            public Double getWeight() { 
                return weight;
            }
    
            public void setWeight(Double weight) { 
                this.weight = weight;
            }
    
            public Double getValue() { 
                return value;
            }
    
            public void setValue(Double value) { 
                this.value = value;
            }
    
            public Double getValWghtRate() { 
                return valWghtRate;
            }
    
            public void setValWghtRate(Double valWghtRate) { 
                this.valWghtRate = valWghtRate;
            }
    
            public Integer getOrder() { 
                return order;
            }
    
            public void setOrder(Integer order) { 
                this.order = order;
            }
    
            public Integer getSelect() { 
                return select;
            }
    
            public void setSelect(Integer select) { 
                this.select = select;
            }
    
            @Override
            public String toString() { 
                return "Item{" +
                        "weight=" + weight +
                        ", value=" + value +
                        ", order=" + order +
                        '}';
            }
        }
    }

### 2.2.运行结果 ###

![image-20211014205116546][]

这里可以看出，在这个算例中，找到了最优解，而且和穷举法结果一样。这是不是就意味着贪心算法就可以解决最优化问题呢？答案是否定的。贪心算法不仅仅是简单的局部最优这么简单，他最终的结果跟贪心的方式是密切相关的。比如上面我们每次选择的是价值重量比最大的物品，也可以每次拿价值最大的物品，这样得到的结果就会不一样。

因为上面的代码的时间复杂度是O(n)，在问题规模变大时，贪心算法计算消耗的时间就会远远小于穷举法，是平缓的线性增长。贪心算法其实就是一个“构造”解的过程而已，相比较于枚举法而言，贪心是没有“搜索”这一过程的，他只是按照一定的方式，将解给构造起来而已。

对于TSP问题的Greedy算法解决，其思想是随机生成第一个城市，加入cityList，然后从剩下城市中，依次找离cityList最后一个城市最近的放进cityList中。

如果决策的每一步之间是独立的，通过设计出优秀的贪心策略，可以取得比较不错的结果，这个时候可以选择贪心算法。这种情况通常可以将整个问题的各个步骤的决策重新分解为一个一个独立的子问题，各个子问题互不影响，贪心获得子问题的最优，组合起来就是全局最优解。

决策的每一步之间是不是独立的，选择贪心方式求解，不可能出现求出的解不能用的情况。

### 2.3.总结 ###

贪心算法的特点：

1.  贪心算法通过“构造”的方式求解，没有“搜索”的过程，算法的时间复杂度是O(n)，随问题规模的增长是平缓的线性增长。
2.  决策的每一步之间是独立的，通过设计出优秀的贪心策略，可以取得比较不错的结果，有时候甚至能找到最优解。
3.  决策的每一步之间是不是独立的，选择贪心方式求解的结果可能会有很大问题。

## 三、启发式算法 ##

问题规模大时，穷举法时间太长没法用；问题复杂时，贪心算法的结果质量太差；所以就需要找到一条既能够得到一个比较优质的解，又能将求解资源控制在一定范围内的算法。这就出现了启发式算法。

启发式算法就是在一个合理的求解资源范围内（合理的时间，合理的内存开销等）求得一个较为满意的解。该解毫无疑问，是要优于或等于贪心解，有可能达到枚举法求得的最优解。

### 3.1.全局搜索和局部搜索 ###

在介绍启发式算法之前，先了解一下全局搜索和局部搜索。

算法的本质就是在解空间（解空间中包括可行解和不可行解）中搜索出最优解。穷举法是构建出解所有的情况，然后验证每种情况，从而找到最优解，所以穷举法需要遍历整个解空间，是全局搜索的过程，当问题规模增大时，其解空间就会变得很大很大，全局搜索的效率就会很低，需要的时间复杂度或空间复杂度是无法接受的。

全局搜索不能接受时，可以使用局部搜索：不完全遍历解空间，只挑一部分出来进行遍历，就可以大大降低搜索需要的资源消耗，同时也可能在局部中找到最优解，或者还不错的一个解。

通常考察一个算法的性能通常用局部搜索能力和全局收敛能力这两个指标。\*\*局部搜索是指能够无穷接近最优解的能力，而全局收敛能力是指找到全局最优解所在大致位置的能力。\*\*局部搜索能力和全局搜索能力，缺一不可。向最优解的导向，对于任何智能算法的性能都是很重要的。

### 3.2.盲目搜索和启发式搜索 ###

按照预定的策略进行解的搜索，在搜索过程中获取的中间信息不用于改进后续的搜索策略，称之为盲目搜索（比如穷举法、蒙塔卡罗模拟）。反之，如果利用了中间的信息来改进搜索策略则称之为启发式搜索（比如爬山算法、模拟退火算法、粒子群算法、遗传算法、蚁群算法等）。

关于“启发式”，可以简单总结为一下亮点：

1.  任何有助于找到问题最优解，但不能保证找到最优解的方法均是启发式方法；
2.  有助于加速求解过程和找到较优解方法是启发式方法。

盲目搜索的执行过程大致是：首先，随机生成很多组解，然后验证这些解是否满足约束条件，若满足则将其保存到一个“可行集”中，然后计算这个可行集内的每个解对应的目标函数值，最后找到最值即可。穷举法和蒙塔卡罗模拟的区别是解空间的生成：蒙塔卡罗模拟解空间中的解是随机生成的，穷举法可能是按照一定的规则生成的（比如步长）。

### 3.3.启发式搜索 ###

启发式算法目前主要包括**邻域搜索**和**群体仿生**两大类。群体仿生类比如遗传算法、模拟退火算法、粒子群算法、蚁群算法等，这些智能搜索也叫元启发式搜索。

具体相关的算法，在其他文章中单独介绍介绍过。

[image-20211014175529798]: /images/20220828/0c71709f7d1c4cf9ad545b9cb63a122f.png
[image-20211014205116546]: /images/20220828/0722af882fd645d6901af34f33537643.png