java贪心算法案例

╰半橙微兮° 2024-03-17 22:28 101阅读 0赞

### 1.零钱找回问题 ###

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。

### 2.背包问题: ###

背包容量=50； w\[\]=\{10,20,30\} ,p\[\]=\{60,100,120\} 用贪心选择（10+20）<50，p=160，但这并不是最优解，事实上(20+30)=50,p=100+120=220.才是问题的解。对于01背包，贪心采用自上而下，拆分子问题的方式为：\{物品1，物品2，物品3\}—>\{物品2，物品3\}----\{物品3\}…它无法保证最终能将背包装满,部分闲置的背包空间使每千克背包空间的价值降低了.  
对于该问题，我们应该采用自下而上的动态规划来求解，拆分子问题的 方式为：\{物品1\}-------->\{物品1，物品2\}------>\{物品1，物品2，物品3\}.在求解时,应比较，选择该物品和不选择该物品，所导致的最终方案,然后再做出最好选择，为了更快求出问题的解。动态规划还记忆了过程中产生的许多互相重叠的子问题的答案。

### 代码 ###

import cn.hutool.core.collection.CollUtil;
    
    import java.util.*;
    
    /**
     * desc: 算法测试
     *
     * @author qts
     * @date 2023/7/19 0019
     */
    public class AlgorithmTest {
    
    
    
        public static void main(String[] args) {
            // 测试找零钱
            //System.out.println(change(320));
    
            // 测试背包问题
            List<HashMap<String, Object>> maps = new ArrayList<>();
            HashMap<String, Object> map = new HashMap<String, Object>();
            map.put("weight", 10f);
            map.put("value",60f);
            map.put("name", "物品1");
            maps.add(map);
    
            map = new HashMap<String, Object>();
            map.put("weight", 30f);
            map.put("value",120f);
            map.put("name", "物品3");
            maps.add(map);
    
            map = new HashMap<String, Object>();
            map.put("weight", 20f);
            map.put("value",100f);
            map.put("name", "物品2");
            maps.add(map);
    
            sortByUnitValue(maps);
            System.out.println("物品列表: "+maps);
    
            List backpack = backpack(50f, maps.toArray(new HashMap[3]));
    
            System.out.println("结果: "+backpack);
    
        }
    
        // 钱面值
        public static int[] moneys = {100, 50, 20, 10, 5, 2, 1};
        // 对应面值的数量
        public static int[] counts = {5, 3, 0, 1, 2, 0, 3};
    
        /**
         * 贪心算法: 找零钱
         * @param amount 金额
         */
        public static String change(int amount) {
            StringBuilder result = new StringBuilder(amount + " = ");
    
            for (int i = 0; i < moneys.length; i++) {
                if (amount <= 0) {
                    break;
                }
    
                int curMoneyCount = Math.min(amount / moneys[i], counts[i]);
    
                amount = amount - curMoneyCount * moneys[i];
                if (curMoneyCount > 0) {
                    if (i > 0) {
                        result.append(" + ");
                    }
                    result.append(curMoneyCount).append("张").append(moneys[i]);
                }
    
            }
    
            if (amount > 0) {
                return "无解";
            }
    
            return result.toString();
        }
    
    
        /**
         * 单位价值倒序
         * @param maps
         */
        private static void sortByUnitValue(List<HashMap<String, Object>> maps) {
            CollUtil.sort(maps, new Comparator<HashMap<String, Object>>() {
                @Override
                public int compare(HashMap<String, Object> o1, HashMap<String, Object> o2) {
                    Float weight1 = (Float) o1.get("weight");
                    Float value1 = (Float) o1.get("value");
                    Float unitValue1 = value1/weight1; // 单位重量的价值
    
                    Float weight2 = (Float) o2.get("weight");
                    Float value2 = (Float) o2.get("value");
                    Float unitValue2 = value2/weight2; // 单位重量的价值
    
                    return (int) ((unitValue2 - unitValue1));
                }
            });
        }
    
        /**
         * 贪心算法: 背包问题
         * @param capacity 背包容量
         * @param maps 物品,从最优到最次排序
         * @return
         */
        public static List<HashMap<String,Object>> backpack(Float capacity,HashMap<String,Object>[] maps) {
            List<HashMap<String,Object>> result = new ArrayList<HashMap<String, Object>>();
    
            for (int i = 0; i < maps.length; i++) {
                if (capacity <= 0) {
                    break;
                }
    
                HashMap<String, Object> goods = maps[i];
                Float weight = (Float) goods.get("weight");// 重量
                Float value = (Float) goods.get("value");// 价值
                String name = (String) goods.get("name");// 名称
    
                Float unitValue = value/weight; // 单位重量的价值
    
                float min = Math.min(capacity, weight);
    
                capacity -= min;// 剩余背包容量
    
                HashMap<String, Object> map = new HashMap<>();
                map.put("weight",min);
                map.put("name",name);
    
                result.add(map);
            }
    
            return result;
    
        }
    
    }

结果:  
![在这里插入图片描述][3986ec23278e4004adf581cbb8ef5ccf.png]

[3986ec23278e4004adf581cbb8ef5ccf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a8684ca1f35e45c8812c2155823fb82f.png