觉得不错请按下图操作，掘友们，哈哈哈！！！

一、背景介绍

如何完成一个通用的优惠算法，而且利用有限资源能够敏捷的核算出优惠结果是一件十分难的工作。在实践场景中咱们很或许在某些业务中装备许多优惠，但是优惠的核算逻辑一般相对杂乱的有的要利用穷举，动态规划，广度优先分包，深度优先核算，再则利用贪心算法等等。或许最后假如真的有许多挑选，咱们还要恰当抉择核算的深度。

选座在咱们实践生活中十分常见，就跟咱们上学的时候选座位相同，首要大家会公认一个最有方位，比方咱们当时是第二排中间认为是最佳方位。比方演唱会中，接近舞台中央的咱们是最佳方位，然后按照此最佳方位向外辐射。还有便是有最佳方位后咱们还要考虑用户挑选，比方说必须要连坐，前后排等相应需求。假如用户没有要求，咱们要供给一种最优挑选，比方在默许连坐的基础上选取最佳区域场景，又或者不考虑连坐只考虑最优方位等场景。如何完成上述所得场景需求，肯定是要有必定的算法支撑。

二：优惠算法

2.1 例子

在咱们现有业务中关于用户买票咱们装备了各种优惠，恣意大礼包可无限次购买。比方说现在有 A 和 B 两种物品，价格分别为 2元和 5元，

优惠 1 ，你能够以 5元的价格购买 3A 和 0B 。
优惠 2 ，你能够以 10 的价格购买 1A 和 2B 。

咱们现在需求购买 3 个 A 和 2 个 B ，

假如原价买 A：3 * 2= 6元；原价买 B： 2*5 =10 元，总价加起来为16元
运用优惠1：付 10元购买 1A 和 2B（优惠 2），以及 4元购买 2A 总价 14元。
运用优惠2：付 5元购买 3A 和 0B（优惠 1），以及 10元购买 2B 总价 15元。

针对这个例子对应贪心算法：

import java.util.HashMap;
import java.util.Map;
public class TicketDiscountCalculator {
    private static final Map<String, int[]> discounts = new HashMap<>();
    static {
        // 初始化优惠规矩
        discounts.put("优惠1", new int[]{3, 0, 5});  // 3A 0B，价格为5元
        discounts.put("优惠2", new int[]{1, 2, 10}); // 1A 2B，价格为10元
    }
    public static int calculateBestPrice(int targetA, int targetB) {
        int totalPrice = Integer.MAX_VALUE;
        for (Map.Entry<String, int[]> entry : discounts.entrySet()) {
            String discountName = entry.getKey();
            int[] discount = entry.getValue();
            int discountA = discount[0];
            int discountB = discount[1];
            int discountPrice = discount[2];
            int numDiscountsA = targetA / discountA;
            int numDiscountsB = targetB / discountB;
            int numDiscounts = Math.min(numDiscountsA, numDiscountsB);
            int remainingA = targetA - numDiscounts * discountA;
            int remainingB = targetB - numDiscounts * discountB;
            int price = numDiscounts * discountPrice + remainingA * 2 + remainingB * 5;
            totalPrice = Math.min(totalPrice, price);
        }
        return totalPrice;
    }
    public static void main(String[] args) {
        int targetA = 3;
        int targetB = 2;
        int bestPrice = calculateBestPrice(targetA, targetB);
        System.out.println("购买 " + targetA + " 个A和 " + targetB + " 个B的最佳价格为：" + bestPrice);
    }
}

2.2 动态规划算法核算最佳优惠

import java.util.HashMap;
import java.util.Map;
public class BestDiscountCalculator {
    private static final Map<Integer, Double> discountRates = new HashMap<>();
    static {
        // 界说不同产品数量对应的扣头率
        discountRates.put(3, 0.8);  // 三件产品8折
        discountRates.put(5, 0.7);  // 五件产品7折
        discountRates.put(10, 0.5); // 十件产品5折
    }
    public static double calculateBestDiscount(int quantity) {
        if (quantity <= 0) {
            return 0.0; // 数量为0或负数，没有扣头可享用
        }
        double[] dp = new double[quantity + 1]; // 动态规划数组，dp[i]表明购买i件产品的最佳优惠金额
        for (int i = 1; i <= quantity; i++) {
            dp[i] = dp[i - 1] + 1; // 默许状况下，不享用任何优惠，优惠金额为1
            for (Map.Entry<Integer, Double> entry : discountRates.entrySet()) {
                int discountQuantity = entry.getKey();
                double discountRate = entry.getValue();
                if (i >= discountQuantity) {
                    dp[i] = Math.min(dp[i], dp[i - discountQuantity] * discountRate);
                }
            }
        }
        return dp[quantity];
    }
    public static void main(String[] args) {
        int quantity = 7; // 假定购买7件产品
        double bestDiscount = calculateBestDiscount(quantity);
        System.out.println("购买 " + quantity + " 件产品的最佳优惠金额为：" + bestDiscount);
    }
}

要完成依据产品数量享用不同优惠并核算出最佳优惠的算法，您能够运用动态规划办法来处理这个问题。以下是一个示例的Java完成：

javaCopy code
import java.util.HashMap;
import java.util.Map;
public class BestDiscountCalculator {
    private static final Map<Integer, Double> discountRates = new HashMap<>();
    static {
        // 界说不同产品数量对应的扣头率
        discountRates.put(3, 0.8);  // 三件产品8折
        discountRates.put(5, 0.7);  // 五件产品7折
        discountRates.put(10, 0.5); // 十件产品5折
    }
    public static double calculateBestDiscount(int quantity) {
        if (quantity <= 0) {
            return 0.0; // 数量为0或负数，没有扣头可享用
        }
        double[] dp = new double[quantity + 1]; // 动态规划数组，dp[i]表明购买i件产品的最佳优惠金额
        for (int i = 1; i <= quantity; i++) {
            dp[i] = dp[i - 1] + 1; // 默许状况下，不享用任何优惠，优惠金额为1
            for (Map.Entry<Integer, Double> entry : discountRates.entrySet()) {
                int discountQuantity = entry.getKey();
                double discountRate = entry.getValue();
                if (i >= discountQuantity) {
                    dp[i] = Math.min(dp[i], dp[i - discountQuantity] * discountRate);
                }
            }
        }
        return dp[quantity];
    }
    public static void main(String[] args) {
        int quantity = 7; // 假定购买7件产品
        double bestDiscount = calculateBestDiscount(quantity);
        System.out.println("购买 " + quantity + " 件产品的最佳优惠金额为：" + bestDiscount);
    }
}

在上述示例中，咱们运用动态规划数组 dp 来记载购买不同数量产品时的最佳优惠金额。咱们首要将默许的优惠金额设置为1，表明不享用任何优惠时的总金额。然后，咱们遍历从1到方针产品数量的一切状况，关于每种状况，咱们考虑是否能够享用不同数量的产品的优惠，并挑选其间最小的优惠金额作为最佳优惠。

请注意，此算法假定扣头是能够叠加运用的，即能够一起享用多个扣头。假如扣头不能叠加运用，则需求相应地修正算法逻辑。

2.3 贪心算法核算最佳优惠

import java.util.HashMap;
import java.util.Map;
public class BestDiscountCalculator {
    private static final Map<Integer, Double> discountRates = new HashMap<>();
    static {
        // 界说不同产品数量对应的扣头率
        discountRates.put(3, 0.8);  // 三件产品8折
        discountRates.put(5, 0.7);  // 五件产品7折
        discountRates.put(10, 0.5); // 十件产品5折
    }
    public static double calculateBestPrice(int quantity) {
        if (quantity <= 0) {
            return 0.0; // 数量为0或负数，总价格为0
        }
        double totalPrice = 0.0;
        while (quantity > 0) {
            int maxDiscountQuantity = 0;
            double maxDiscountRate = 1.0;
            for (Map.Entry<Integer, Double> entry : discountRates.entrySet()) {
                int discountQuantity = entry.getKey();
                double discountRate = entry.getValue();
                if (discountQuantity <= quantity && discountRate < maxDiscountRate) {
                    maxDiscountQuantity = discountQuantity;
                    maxDiscountRate = discountRate;
                }
            }
            if (maxDiscountQuantity > 0) {
                int numDiscounts = quantity / maxDiscountQuantity;
                totalPrice += numDiscounts * maxDiscountRate * maxDiscountQuantity;
                quantity -= numDiscounts * maxDiscountQuantity;
            } else {
                totalPrice += quantity; // 没有可享用的扣头，按原价核算剩下产品数量的价格
                break;
            }
        }
        return totalPrice;
    }
    public static void main(String[] args) {
        int quantity = 12; // 假定购买12件产品
        double bestPrice = calculateBestPrice(quantity);
        System.out.println("购买 " + quantity + " 件产品的最佳价格为：" + bestPrice);
    }
}

在上述示例中，咱们运用discountRates映射存储不同产品数量和对应的扣头率。在calculateBestDiscount办法中，咱们运用一个while循环，不断挑选能够享用的最大扣头并核算优惠金额，直到产品数量为0或无法享用更多扣头为止。

在while循环中，咱们首要初始化maxDiscountQuantity和maxDiscountRate为0和1.0，分别表明当时可享用的最大扣头的产品数量和扣头率。然后，咱们遍历discountRates映射中的每个扣头率，找到满意以下条件的最大扣头：产品数量不超越剩下产品数量，且扣头率更低。假如找到了最大扣头，咱们核算能够享用的该扣头。贪心算法或许不必定能够找到大局最优解，但在某些状况下能够供给近似的最佳处理方案。详细完成取决于您的详细要求和业务逻辑。

三：选座算法

为了规划一个最佳座位选座算法，能够考虑以下因素：

座位排列：首要，需求考虑座位的排列方式，比方是一字排开还是成对连座。这会影响到后续算法的完成。

优先级：确认顾客选座的优先级，例如老人、残疾人、孕妇、儿童等或许需求考虑优先组织。

连座需求：假如顾客有连座需求，算法应该考虑到尽量满意他们的要求。这能够是朋友、家人或集体需求连在一起。

已选座位：假如有现已选定的座位，算法需求考虑这些座位的方位，以确保其他顾客有杰出的挑选。

基于以上考虑，以下是一个简单的最佳座位选座算法的示例：

初始化座位矩阵，记载每个座位的状况（可用、已选、不可用等）。

依据优先级规矩的顺序，遍历顾客列表。

关于每个顾客，首要检查是否有连座需求。假如有，寻找连续的座位以满意需求。能够运用贪心算法，从左到右遍历座位矩阵，找到第一个满意连座需求的方位。

假如没有连座需求或无法满意连座需求，持续遍历座位矩阵，找到最佳的单个座位。能够依据一些启发式规矩，比方挑选接近舞台、走道或紧迫出口的座位。

标记已选定的座位。

重复过程3到5，直到一切顾客都被组织座位或没有可用座位。

这仅仅一个简单的示例算法，实践状况或许愈加杂乱，需求依据详细需求进行调整和改进。例如，能够考虑更杂乱的座位评估指标，考虑顾客之间的间隔。别的，算法的性能还能够经过运用动态规划或其他优化技术来进步。

3.1 贪心算法完成

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
class Seat {
    private int row;
    private int number;
    private boolean isTaken;
    public Seat(int row, int number) {
        this.row = row;
        this.number = number;
        this.isTaken = false;
    }
    public int getRow() {
        return row;
    }
    public int getNumber() {
        return number;
    }
    public boolean isTaken() {
        return isTaken;
    }
    public void setTaken(boolean taken) {
        isTaken = taken;
    }
}
class Customer {
    private String name;
    private boolean requireAdjacentSeats;
    public Customer(String name, boolean requireAdjacentSeats) {
        this.name = name;
        this.requireAdjacentSeats = requireAdjacentSeats;
    }
    public String getName() {
        return name;
    }
    public boolean requireAdjacentSeats() {
        return requireAdjacentSeats;
    }
}
class SeatSelectionAlgorithm {
    public List<Seat> selectSeats(List<Customer> customers, int numRows, int seatsPerRow) {
        List<Seat> seats = createSeats(numRows, seatsPerRow);
        PriorityQueue<Seat> pq = new PriorityQueue<>(Comparator.comparingInt(this::calculateSeatScore));
        pq.addAll(seats);
        List<Seat> selectedSeats = new ArrayList<>();
        for (Customer customer : customers) {
            Seat selectedSeat = null;
            if (customer.requireAdjacentSeats()) {
                selectedSeat = selectAdjacentSeats(pq, 2); // 挑选连座
            }
            if (selectedSeat == null) {
                selectedSeat = selectBestSeat(pq); // 挑选最佳单个座位
            }
            if (selectedSeat != null) {
                selectedSeat.setTaken(true);
                selectedSeats.add(selectedSeat);
            }
        }
        return selectedSeats;
    }
    private List<Seat> createSeats(int numRows, int seatsPerRow) {
        List<Seat> seats = new ArrayList<>();
        for (int row = 1; row <= numRows; row++) {
            for (int number = 1; number <= seatsPerRow; number++) {
                seats.add(new Seat(row, number));
            }
        }
        return seats;
    }
    private Seat selectAdjacentSeats(PriorityQueue<Seat> pq, int numAdjacentSeats) {
        Seat selectedSeat = null;
        List<Seat> consecutiveSeats = new ArrayList<>();
        while (!pq.isEmpty()) {
            Seat seat = pq.poll();
            if (!seat.isTaken()) {
                consecutiveSeats.add(seat);
                if (consecutiveSeats.size() == numAdjacentSeats) {
                    selectedSeat = consecutiveSeats.get(consecutiveSeats.size() - 1);
                    break;
                }
            } else {
                consecutiveSeats.clear();
            }
        }
        for (Seat seat : consecutiveSeats) {
            pq.offer(seat);
        }
        return selectedSeat;
    }
    private Seat selectBestSeat(PriorityQueue<Seat> pq) {
        Seat selectedSeat = pq.poll();
        while (selectedSeat != null && selectedSeat.isTaken()) {
            selectedSeat = pq.poll();
        }
        return selectedSeat;
    }
    private int calculateSeatScore(Seat seat) {
        // 你能够依据需求界说座位评分规矩，例如离舞台近的座位分数更高
        return seat.getRow() * seat.getNumber();
    }
}
public class Main {
    public static void main(String[] args) {
        List<Customer> customers = new ArrayList<>();
        customers.add(new Customer("Alice", false));
        customers.add(new Customer("Bob", true));
        customers.add(new Customer("Charlie", false));
        customers.add(new Customer("Dave", true));
        SeatSelectionAlgorithm algorithm = new SeatSelectionAlgorithm();
        List<Seat> selectedSeats = algorithm.selectSeats(customers, 10, 8);
        for (Seat seat : selectedSeats) {
            System.out.println("Selected seat: Row " + seat.getRow() + ", Seat " + seat.getNumber());
        }
    }
}

这个示例中，Seat 类表明座位，Customer 类表明顾客，SeatSelectionAlgorithm 类完成了选座算法。selectSeats 办法接受顾客列表、座位行数和每行座位数作为输入，回来一个包含所选座位的列表。selectAdjacentSeats 办法用于挑选连座，selectBestSeat 办法用于挑选最佳单个座位。calculateSeatScore 办法用于核算座位的评分，能够依据需求界说评分规矩。请注意，这仅仅一个简化的示例，实践状况或许愈加杂乱，你能够依据实践需求进行调整和改进评分规矩以及其他算法细节。

3.2 曼哈顿间隔求最佳座位

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
class Seat {
    private int row;
    private int column;
    private boolean isTaken;
    public Seat(int row, int column) {
        this.row = row;
        this.column = column;
        this.isTaken = false;
    }
    public int getRow() {
        return row;
    }
    public int getColumn() {
        return column;
    }
    public boolean isTaken() {
        return isTaken;
    }
    public void setTaken(boolean taken) {
        isTaken = taken;
    }
}
class Customer {
    private String name;
    private boolean requireAdjacentSeats;
    private int requiredRow;
    private int requiredColumn;
    public Customer(String name, boolean requireAdjacentSeats, int requiredRow, int requiredColumn) {
        this.name = name;
        this.requireAdjacentSeats = requireAdjacentSeats;
        this.requiredRow = requiredRow;
        this.requiredColumn = requiredColumn;
    }
    public String getName() {
        return name;
    }
    public boolean requireAdjacentSeats() {
        return requireAdjacentSeats;
    }
    public int getRequiredRow() {
        return requiredRow;
    }
    public int getRequiredColumn() {
        return requiredColumn;
    }
}
class SeatSelectionAlgorithm {
    public List<Seat> selectSeats(List<Customer> customers, int numRows, int numColumns, int centerRow, int centerColumn) {
        List<Seat> seats = createSeats(numRows, numColumns);
        seats.sort(Comparator.comparingInt(this::calculateSeatScore)); // 按座位评分升序排序
        List<Seat> selectedSeats = new ArrayList<>();
        for (Customer customer : customers) {
            Seat selectedSeat = null;
            if (customer.requireAdjacentSeats()) {
                selectedSeat = selectAdjacentSeats(seats, customer.getRequiredRow(), customer.getRequiredColumn(), 2); // 挑选连坐
            }
            if (selectedSeat == null) {
                selectedSeat = selectBestSeat(seats, customer.getRequiredRow(), customer.getRequiredColumn()); // 挑选最佳单个座位
            }
            if (selectedSeat != null) {
                selectedSeat.setTaken(true);
                selectedSeats.add(selectedSeat);
            }
        }
        return selectedSeats;
    }
    private List<Seat> createSeats(int numRows, int numColumns) {
        List<Seat> seats = new ArrayList<>();
        for (int row = 1; row <= numRows; row++) {
            for (int column = 1; column <= numColumns; column++) {
                seats.add(new Seat(row, column));
            }
        }
        return seats;
    }
    private Seat selectAdjacentSeats(List<Seat> seats, int requiredRow, int requiredColumn, int numAdjacentSeats) {
        int consecutiveCount = 0;
        Seat selectedSeat = null;
        for (Seat seat : seats) {
            if (!seat.isTaken() && seat.getRow() == requiredRow && seat.getColumn() >= requiredColumn) {
                consecutiveCount++;
                if (consecutiveCount == numAdjacentSeats) {
                    selectedSeat = seat;
                    break;
                }
            } else {
                consecutiveCount = 0;
            }
        }
        return selectedSeat;
    }
    private Seat selectBestSeat(List<Seat> seats, int requiredRow, int requiredColumn) {
        Seat selectedSeat = null;
       for (Seat seat : seats) {
            if (!seat.isTaken() && seat.getRow() == requiredRow && seat.getColumn() >= requiredColumn) {
                selectedSeat = seat;
                break;
            }
        }
        return selectedSeat;
    }
    private int calculateSeatScore(Seat seat) {
        int distanceFromCenter = Math.abs(seat.getRow() - centerRow) + Math.abs(seat.getColumn() - centerColumn);
        return distanceFromCenter;
    }
}
public class Main {
    public static void main(String[] args) {
        List<Customer> customers = new ArrayList<>();
        customers.add(new Customer("Alice", true, 5, 4));
        customers.add(new Customer("Bob", false, 7, 6));
        customers.add(new Customer("Charlie", true, 3, 2));
        customers.add(new Customer("Dave", false, 6, 5));
        SeatSelectionAlgorithm algorithm = new SeatSelectionAlgorithm();
        List<Seat> selectedSeats = algorithm.selectSeats(customers, 10, 10, 5, 5);
        for (Seat seat : selectedSeats) {
            System.out.println("Selected seat: Row " + seat.getRow() + ", Column " + seat.getColumn());
        }
    }
}

在这个示例中，咱们引入了座位的行和列，以便更精确地确认最佳方位。一起，咱们运用了曼哈顿间隔（座位行和列的绝对差之和）作为座位评分的依据，间隔越小的座位评分越高。，咱们创建了一个顾客列表，调用 selectSeats 办法进行座位选取，并输出所选座位的信息。这仅仅一个简化的示例，实践状况或许愈加杂乱，你能够依据实践需求进行调整和改进评分规矩以及其他算法细节。

参阅： 1386. 组织电影院座位

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        int left = 0b11110000;
        int middle = 0b11000011;
        int right = 0b00001111;
        Map <Integer, Integer> occupied = new HashMap <Integer, Integer> ();
        for (int[] seat: reservedSeats) {
            if (seat[1] >= 2 && seat[1] <= 9) {
                int origin = occupied.containsKey(seat[0]) ? occupied.get(seat[0]) : 0;
                int value = origin | (1 << (seat[1] - 2));
                occupied.put(seat[0], value);
            }
        }
        int ans = (n - occupied.size()) * 2;
        for (Map.Entry <Integer, Integer> entry : occupied.entrySet()) {
            int row = entry.getKey(), bitmask = entry.getValue();
            if (((bitmask | left) == left) || ((bitmask | middle) == middle) || ((bitmask | right) == right)) {
                ++ans;
            }
        }
        return ans;
    }
}

重视不迷路，后续会迁移微信大众号上：

往期经典：

【干货】运用Canal 处理数据同步场景中的疑难杂症！！！

【干货】常见库存规划方案-各种方案对比总有一个适合你

JYM来一篇音讯行列-Kafaka的干货吧！！！

规划形式：

JYM 规划形式系列- 单例形式，适配器形式，让你的代码更高雅！！！

JYM 规划形式系列- 职责链形式，装修形式，让你的代码更高雅！！！

JYM 规划形式系列- 策略形式，模板办法形式，让你的代码更高雅！！！

JYM 规划形式系列-工厂形式，让你的代码更高雅！！！

Spring相关：

Spring源码解析-陈词滥调Bean ⽣命周期，但这个你值得看！！！

Spring 源码解析-JYM你值得拥有，从源码角度看bean的循环依赖！！！

Spring源码解析-Spring 业务

本文正在参加「金石计划」

【干货】最佳优惠算法；最佳座位算法分析

一、背景介绍

二：优惠算法

2.1 例子

2.2 动态规划算法核算最佳优惠

2.3 贪心算法核算最佳优惠

三：选座算法

3.1 贪心算法完成

3.2 曼哈顿间隔求最佳座位

往期经典：

作者信息

推广

【干货】 最佳优惠算法；最佳座位算法分析

一、背景介绍

二：优惠算法

2.1 例子

2.2 动态规划算法核算最佳优惠

2.3 贪心算法核算最佳优惠

三：选座算法

3.1 贪心算法完成

3.2 曼哈顿间隔求最佳座位

往期经典：

相关文章

C++学习6（10.7-10.8）

python动态导入模块import_module 和 重载reload

写给 Android 开发的小程序布局指南，Flex 布局！

大数据时代，数据仓库究竟是干嘛的？

作者信息

推广

【干货】最佳优惠算法；最佳座位算法分析

python动态导入模块import_module 和重载reload