贪心算法

贪心算法

每一步都采取最优的做法，每步都是局部最优解，最终得到的就是全局最优解。贪心算法是一个近似算法，而不是最优解算法

以背包算法为例，有一个小偷，背包可装35磅重的东西，在商场准备偷取商品放入背包。力图往背包中装入价值最高的商品。使用贪心算法，分为两步

• 盗窃可装入背包的最贵的商品
• 再盗窃还可装入背包的最贵商品，以此类推

是不是很简单，但是使用该算法得到的不是最优解。有如下商品：

• 音响 3000元 30磅
• 笔记本电脑 2000元 20磅
• 吉他 1500元 15磅

使用贪心算法的话得到的是音响，价格为3000元。而实际偷取笔记本电脑和吉他价格为3500元

public class TXProblem {

    public static void main(String[] args) {
        Goods[] bags = new Goods[]{
                new Goods("吉他",15, 1500),
                new Goods("音响",30, 3000),
                new Goods("笔记本电脑",20, 2000),

        };
        int totalWeight = 35;

        TXSFProblem problem = new TXSFProblem(bags, totalWeight);
        problem.solve();
        System.out.println("背包内物品："+problem.getInBags());
        System.out.println("最大价值："+problem.getBestValue());
        

    }


    static class Goods implements Comparable<Goods> {
        /**
         * 物品重量
         */
        private int weight;
        /**
         * 物品价值
         */
        private int value;
        /**
         * 单位重量价值
         */
        private String name;

        public Goods(String name,int weight, int value) {
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public int compareTo(Goods goods) {
            return Integer.compare(this.value,goods.value);
        }
    }


    static class TXSFProblem {
        // 现有的物品
        private Goods[] goods;
        // 背包的总承重
        private int totalWeight;
        // 背包最大总价值
        private int bestValue;
        // 背包中的物品
        private Set<String> inBags = new HashSet<>();

        public Set<String> getInBags() {
            return inBags;
        }

        public TXSFProblem(Goods[] goods, int totalWeight) {
            this.goods = goods;
            this.totalWeight = totalWeight;        // 对背包按单位重量价值从大到小排序
            Arrays.sort(goods, Collections.reverseOrder());
        }

        public void solve() {
            int tempWeight = totalWeight;
            for (int i = 0; i < goods.length; i++) {
                //判断当前物品是否可以放入背包中，若不能则继续循环，查找下一个物品
                if (tempWeight - goods[i].getWeight() < 0)
                    continue;
                tempWeight -= goods[i].getWeight();
                bestValue += goods[i].getValue();
                inBags.add(goods[i].name);
            }
        }

        public int getBestValue() {
            return bestValue;
        }
    }
}

结果为

最大价值：3000
背包内物品：[音响]