java贪心算法

迷南。 2021-06-10 20:38 458阅读 0赞

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。  
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。[百度百科介绍传送门][Link 1]

举一个简单的例子  
有一个背包，最多能承载150斤的重量，现在有7个物品，重量分别为\[35, 30, 60, 50, 40, 10, 25\]，它们的价值分别为\[10, 40, 30, 50, 35, 40, 30\]，如果是你的话，应该如何选择才能使得我们的背包背走最多价值的物品？

个人思路分析，也就是贪心算法的思路，通过求性价比，然后排序性价比，最后从性价比最大的开始选择，直到装满为止，这就是贪心算法的思路。下面上代码

/**
     * 贪心算法，我们可以通过求出性价比，然后排序性价比，然后从性价比最大的开始选择，直到装满为止。这就是贪心算法的思路。
     */
    public class BeiBao {
        //定义最大负重，weight数组保存重量，values数组保存价值
        public int max_weight = 150;
        public static int[] weight = new int[] {35,30,60,50,40,10,25};
        public static int[] value = new int[] {10,40,30,50,35,40,30};
        //
        public void greedyPackage(int capacity, int[] weight , int[] value) {
            //性价比数组创建并排序
            int n = weight.length;//总个数
            double[] price = new double[n];//性价比数组
            int count[] = new int[n];//序号数组
    
            //求性价比
            for (int i = 0; i < n; i++) {
                price[i] = (double)value[i] / weight[i];
                System.out.println(price[i]);
                count[i] = i;
            }
    
            //性价比排序
            for (int i = 0; i < n - 1; i++) {
                for (int j = i; j < n - 1; j++) {
                    if (price[j] < price[j + 1]) {
                        double tmp = price[j];
                        price[j] = price[j + 1];
                        price[j + 1] = tmp;
                        //交换性价比排序后，再吧序号交换,方便之后取数
                        int a = count[j];
                        count[j] = count[j + 1];
                        count[j + 1] = a;
                    }
                }
            }
    
            //把质量和价值也按照性价比的排序顺序对应好，存到新数组里
            int newWeight[] = new int[n];
            int newValue[] = new int[n];
            for (int i = 0; i < n; i++) {
                newValue[i] = value[count[i]];
                newWeight[i] = weight[count[i]];
            }
    
            double maxValue = 0;
            //装东西，优先拿性价比高的
            for (int i = 0; i < n; i++) {
                if (capacity > newWeight[i]) {
                    capacity -= newWeight[i];
                    maxValue += newValue[i];
                }
            }
    
            System.out.print("共放下了" + (max_weight - capacity) +"kg重的东西\n");
            System.out.print("总价值" + maxValue);
        }
    
        public static void main(String[] args) {
            BeiBao greedyPackage = new BeiBao();
            greedyPackage.greedyPackage(greedyPackage.max_weight, weight, value);
        }
    }

感谢大佬的高性能版

private void greedyPackageV2(Integer capacity, Integer[] weight , Integer[] value) {
            List<Integer> weightList = Arrays.asList(weight);
            List<Integer> valueList = Arrays.asList(value);
            Map<Integer,Double> price = new HashMap<>();//性价比数组
            List<Integer> count  = new ArrayList<>();
            for (int i = 0; i < weightList.size(); i++) {
                price.put(i, valueList.get(i) / weightList.get(i).doubleValue());
            }
             List<Map.Entry<Integer,Double>> list = new ArrayList<>(price.entrySet()); //将map的entryset放入list集合
            //根据性价比排序并取出倒序序后下标
            list.sort(Comparator.comparing(Map.Entry<Integer,Double>::getValue).reversed());//根据性价比倒序
            list.forEach(entry -> count.add(entry.getKey()));
             double maxValue = 0;
            //装东西，优先拿性价比高的
            for (int i = 0; i < count.size(); i++) {
                if (capacity > weight[count.get(i)]) {
                    capacity -= weight[count.get(i)];
                    maxValue += value[count.get(i)];
                }
            }
            System.out.println("总共放下了" +  (max_weight - capacity)  + "kg重的东西");
            System.out.print("总价值" + maxValue+"\n");
        }

运行结果为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FkbWluUHdk_size_16_color_FFFFFF_t_70]  
如果各位老鸟发现博文有问题，请评论指点谢谢  
大家一起学的可以加一个QQ群`774032881`

[Link 1]: https://baike.baidu.com/item/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/5411800?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FkbWluUHdk_size_16_color_FFFFFF_t_70]: /images/20210522/265b361044834404b005fb015a8f2c49.png