贪心算法

贪心算法：对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的选择是在某种意义上的局部最优解。

贪心算法并不保证会得到最优解。

找零问题

思路：先找最大的100元。再进一步看50元。

package com.algorithm.demo.senior;
import com.google.common.collect.Lists;
import java.util.List;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class ChangeMoney {
    private static List<Integer> list = Lists.newArrayList(100, 50, 20, 5, 1);
    public static void main(String[] args) {
        System.out.println(change(165));
        System.out.println(change(266));
        System.out.println(change(1377));
    }
    public static List<Integer> change(int money) {
        List<Integer> result = Lists.newArrayList();
        for (int i = 0; i < list.size(); i++) {
            int denomination = list.get(i);
            int cur = money / denomination;
            result.add(cur);
            money = money % denomination;
            if (money == 0) {
                break;
            }
        }
        return result;
    }
}

背包问题

package com.algorithm.demo.senior;
import com.alibaba.fastjson.JSONObject;
import com.google.common.collect.Lists;
import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.List;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class FractionalBackpack {
    public static void main(String[] args) {
        List<Goods> goods = Lists.newArrayList(new Goods(60, 10),
                new Goods(100, 20),
                new Goods(120, 30));
        int totalWeight = 50;
        goods.sort(((o1, o2) -> o2.getPrice() / o2.getWeight() - o1.getPrice() / o1.getWeight()));
        System.out.println(JSONObject.toJSONString(goods));
        List<Double> weightGoods = Lists.newArrayList();
        for (Goods curGoods : goods) {
            int curWeight = curGoods.getWeight();
            if (curWeight <= totalWeight) {
                weightGoods.add(new Double("1"));
                totalWeight -= curWeight;
            } else {
                weightGoods.add(totalWeight / (double) curWeight);
                totalWeight = 0;
                break;
            }
        }
        System.out.println(JSONObject.toJSONString(weightGoods));
    }
}
@Data
@AllArgsConstructor
class Goods {
    private int price;
    private int weight;
}

拼接最大数字问题

package com.algorithm.demo.senior;
import com.alibaba.fastjson.JSONObject;
import com.google.common.collect.Lists;
import java.util.List;
import java.util.stream.Collectors;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class NumberJoin {
    public static void main(String[] args) {
        List<String> li = Lists.newArrayList("32", "94", "128", "1286", "6", "71");
        // a = "96" , "b" = "87"
        // a + b = "9687"  b + a = "8796"
        // a + b > b + a
        join(li);
        System.out.println(JSONObject.toJSONString(li));
        System.out.println(li.stream().collect(Collectors.joining()));
    }
    public static void join(List<String> li) {
        // 排序
        li.sort((a, b) -> {
            String xy = a + b;
            String yx = b + a;
            return (int) (Long.parseLong(yx) - Long.parseLong(xy));
        });
    }
}

活动选择问题

怎么贪心？

package com.algorithm.demo.senior;
import com.alibaba.fastjson.JSONObject;
import com.google.common.collect.Lists;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.ToString;
import java.util.List;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class ActivitySelection {
    static List<Activity> activities = Lists.newArrayList(new Activity(1, 4),
            new Activity(3, 5),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(3, 9),
            new Activity(5, 9),
            new Activity(6, 10),
            new Activity(8, 11),
            new Activity(8, 12),
            new Activity(2, 14),
            new Activity(12, 16));
    public static void main(String[] args) {
        List<Activity> res = Lists.newArrayList(activities.get(0));
        for (int i = 1; i < activities.size(); i++) {
            if (activities.get(i).getStart() >= res.get(res.size() - 1).getEnd()) {
                // 不冲突
                // 当前活动的开始时间大于等于最后一个活动的结束时间
                res.add(activities.get(i));
            }
        }
        System.out.println(JSONObject.toJSONString(res));
    }
}
@AllArgsConstructor
@Getter
class Activity {
    int start;
    int end;
}

总结

• 最优化问题
•