觉得不错请按下图操作，掘友们，哈哈哈！！！
一、背景介绍
如何实现一个通用的优惠算法，并且利用有限资源能够迅速的计算出优惠结果是一件非常难的事情。
在现实场景中我们很可能在某些业务中配置很多优惠，但是优惠的计算逻辑一般相对复杂的有的要利用穷举，动态规划，广度优先分包，深度优先计算，再则利用贪心算法等等。可能最后如果真的有很多选择，我们还要适当抉择计算的深度。
选座在我们现实生活中非常常见，就跟我们上学的时候选座位一样，首先大家会公认一个最有位置，比如我们当时是第二排中间认为是最佳位置。比如演唱会中，靠近舞台中央的我们是最佳位置，然后按照此最佳位置向外辐射。还有就是有最佳位置后我们还要考虑用户选择，比如说必须要连坐，前后排等相应需求。如果用户没有要求，我们要提供一种最优选择，比如在默认连坐的基础上选取最佳区域场景，又或者不考虑连坐只考虑最优位置等场景。如何实现上述所得场景需求，肯定是要有一定的算法支撑。
二：优惠算法
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;
}
}
往期经典：
设计模式：
JYM 设计模式系列- 单例模式，适配器模式，让你的代码更优雅！！！
JYM 设计模式系列- 责任链模式，装饰模式，让你的代码更优雅！！！
JYM 设计模式系列- 策略模式，模板方法模式，让你的代码更优雅！！！
Spring相关：
Spring源码解析-老生常谈Bean ⽣命周期 ，但这个你值得看！！！
Spring 源码解析-JYM你值得拥有，从源码角度看bean的循环依赖！！！
本文正在参加「金石计划」
© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END
