贪心算法(被黑心公司强迫写的降薪算法)

package Algorithm;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
/**
 * 降薪问题(贪心算法)
 */
public class TanXinSalary {
    /*
    贪心算法的原理是，在每个选择阶段，都选择当前状态下的最优解，最终得到的结果是全局最优解。
    示例代码中用到了一个类，表示需要降薪的人。然后用knapsack()函数实现贪心算法，
    在实现时先按薪水进行排序，然后逐个添加需要降薪的人，直到降薪人数名额满或者没有人数可选。
    在main()函数中，我们使用6个人和这次降薪批次为满足薪资区间进行测试，输出需要降薪的人。
     */
 
 
    // 定义一个类，包含薪水和人名两个属性(不校验人名重复)
    public static class Item {
        /**
         * 薪水
         */
        private int salary;
        private String name;
 
 
        public Item(int salary, String name) {
            this.salary = salary;
            this.name = name;
        }
 
        public int getSalary() {
            return salary;
        }
 
        public String getName() {
            return name;
        }
    }
 
    /**
     * 定义一个贪心算法实现的函数
     * 注：这个贪心算法实现是不看任何情面，按最高的薪资排序
     * 满足在降薪范围内就进行降薪扣款。平时的什么给你画的饼现在一点卵用都没有。
     *
     * @param items        降薪类
     * @param salaryPeople 降薪总人数
     * @param numMax       降薪区间
     * @return
     */
    public static List<Item> knapsack(List<Item> items, int salaryPeople, int[] numMax) {
        // 根据物品的薪资高的优先降排序（看黑心公司需求-可以写一个映射对照表--重点需要注意）
        Collections.sort(items, Comparator.comparingDouble(Item::getSalary).reversed());
//        items.forEach(item -> System.out.println(item.getSalary()));
        List<Item> result = new ArrayList<>();
        //降薪总值
        int numSalary = 0;
        // 逐个添加降薪人员，直到降薪总人数足够或者没有降薪人数可选
        for (Item item : items) {
            //开始赛选薪资    第一次为0是取第一个人的
            // 如果不为0加上之前的人的薪资，校验是否已经满足了公司的亏损，不满足继续找人降，满足者跳过
            numSalary = numSalary == 0 ? item.getSalary() : numSalary + item.getSalary();
            // 降薪人数小于等于总降薪人数--添加至降薪人数集合--降薪总人数减去添加进去的人数得到剩余降薪人数
            if (checkSalary(numSalary, numMax)) {
                if (salaryPeople > 0) {
                    result.add(item);
                    salaryPeople -= 1;
                    if (salaryPeople == 0) {
                        continue;
                    }
                } else if (salaryPeople == 0) {
                    //降薪总人数满---但是降薪薪资还不满足，则继续降薪赛选人数-为黑心公司创造更多利益
                    result.add(item);
                    if (checkSalary(numSalary, numMax)) {
                        continue;
                    } else {
                        break;
                    }
                }
            }
        }
        return result;
    }
 
    /**
     * 判断降薪总价是否在降薪总区间内
     *
     * @param salary
     * @param numMax
     * @return
     */
    public static boolean checkSalary(int salary, int[] numMax) {
        if (salary >= numMax[0] && salary <= numMax[1] || salary >= numMax[0] && salary <= numMax[2]) {
            return true;
        }
        return false;
    }
 
    public static void main(String[] args) {
        List<Item> items = new ArrayList<>();
        items.add(new Item(21750, "张城阳"));
        items.add(new Item(12600, "王继红"));
        items.add(new Item(15220, "杨凯"));
        items.add(new Item(25120, "李海生"));
        items.add(new Item(31510, "赵户"));
        items.add(new Item(11220, "何璐"));
        items.add(new Item(14418, "石开男"));
        items.add(new Item(28741, "李珠"));
        items.add(new Item(21156, "诺暗"));
        items.add(new Item(42153, "孔爱子"));
        items.add(new Item(22141, "成兰文"));
        items.add(new Item(21001, "孙景卫"));
        items.add(new Item(18154, "梅迪钰"));
        items.add(new Item(19877, "张安茂"));
        int salaryPeople = 6;//降薪人数
        int[] numMax = {16000, 250000, 300000};//降薪区间 最小值/最大值/上限值
        List<Item> result = knapsack(items, salaryPeople, numMax);
        System.out.println("这次降薪人数：" + salaryPeople);
        System.out.println("实际降薪人数：" + result.size());
        System.out.println("降薪人名:");
        int totalValue = 0;
        for (Item item : result) {
            System.out.println("薪水：" + item.getSalary() + ", 人名：" + item.getName());
            totalValue += item.getSalary();
        }
        System.out.println("降薪总额：" + totalValue);
    }
}