接触到一个经典的面试题:类似于背包最优解的问题 原题如下
import java.util.List;
public
class SplitOrders {
public class Item{
/**
* 卖家用户id
*/
long sellerId;
/**
* 商品价格，单位分
*/
long price;
}
public class Order{
/**
* 该订单对应的商品
*/
List<Item> orderItems;
/**
* 该订单金额，单位分
*/
long totalPrice;
/**
* 该订单对应的卖家userId
*/
long sellerId;
}
/**
* 根据
购物车的商品，生成相应的交易订单，根据如下规则
* 1.每笔交易订单可以有多个商品
* 2.每笔交易订单的商品只能是同一个卖家
* 3.每笔交易商品的总价格不能超过1000元
* 4.生成的交易订单数量最小
* @param items：购物车所有商品
*/
public List<Order> packageItemsToOrders(List<Item> items){
return null;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
其实就是一个最优拼单的问题
我的解决思路就是尽量的让一个订单金额趋向于1000,比较简单粗暴
具体思路
1.按照不同卖家进行分组
2.核心原则：通过凑单的方式，将每个订单的总金额趋向1000
将卖家下的商品列表按照价格排序 拆分为一个低价商品列表（升序） 高价商品列表（降序），
3.最高价商品+最低价商品,如果大于1000，将最商品单独高价 作为一个订单，移除列表,最低价商品放回列表，重复上述操作
4.最高价商品+最低价商品，如果小于1000,
循环获取低价列表，与之前结果相加，大于1000则终止，小于1000则继续，
每次获取列表的商品都会通过remove方法，如果商品拼单失败就会原位置放回列表
具体代码如下
// 按照卖家进行分组
public List<Order> separationItems(List<Item> items) {
Map<Long, List<Item>> map = new HashMap<>();
/**
* 按照卖家进行分组，
*/
for (Item item : items) {
Long sellId = item.sellerId;
List<Item> sellerList = map.get(sellId);
if (sellerList == null || sellerList.size() == 0) {
sellerList = new ArrayList<>();
}
sellerList.add(item);
map.put(sellId, sellerList);
}
List<Order> res = new ArrayList<>();
/**
* 以卖家为单位，合并订单
*/
for (Long sellId : map.keySet()) {
List<Order> orderMergeRes = mergeItems(sellId,map.get(sellId));
res.addAll(orderMergeRes);
}
return res;
}
/**
* 商品列表合并操作
* 尽量保证每个订单的总额无限接近1000，将最高价格商品与最低价格相加，如果大于1000
* 则任务最高价格商品
智能
* 以下面为例
* 12,34,45,67,222,555,777,888,999
* 1.999+12，大于1000,则 999 独立为一个订单
* 2.继续将888+12，小于1000,则继续+34,大于1000,将888 34 合并作为一个订单
*
* @param lessThenT
* @return
*/
public List<Order> mergeItems(Long sellId, List<Item> lessThenT) {
Collections.sort(lessThenT);
int len = lessThenT.size();
int flag = len % 2 == 0 ? len / 2 : len / 2 + 1;
// 保存低价商品列表 从小到大排序
List<Item> minList = new ArrayList<>();
// 保存高价商品列表 从大到小
List<Item> maxList = new ArrayList<>(lessThenT);
for (int i = 0; i < flag; i++) {
minList.add(lessThenT.get(i));
maxList.remove(0);
}
Collections.reverse(maxList);
List<Order> orderList = new ArrayList<>();
redo:
while (maxList.size() > 0) {
Item max = maxList.remove(0);
Item min = minList.size()==0?null:minList.remove(0);
/**
* 最高价格商品 无法与其他商品合并为一单
* 或当前低价格已经被消耗完了
*/
if ((min == null || max.price + min.price > 1000)) {
/**
* 合并失败，将商品还回到原处
*/
if(min != null){
minList.add(0, min);
}
List<Item> tmp = new ArrayList<>();
tmp.add(max);
Order order = new Order();
order.orderItems = tmp;
order.totalPrice = max.price;
order.sellerId = sellId;
orderList.add(order);
continue;
} else {
/**
* 如果当前最高价格可以与最低价格合并，则再尝试 与次低价格商品合并
*/
List<Item> tmp = new ArrayList<>();
tmp.add(max);
tmp.add(min);
Long total = max.price + min.price;
redoLow:
while (minList.size() > 0) {
Item minSecond = minList.remove(0);
if ((total + minSecond.price) > 1000) {
minList.add(0, minSecond);
Order order = new Order();
order.orderItems = tmp;
order.totalPrice = total;
order.sellerId = sellId;
orderList.add(order);
// 高价商品提前消耗完了 將低价商品列表 拆分 重复上一步
if (maxList.size() == 0 && minList.size() > 0) {
maxList.add(0, minList.remove(minList.size() - 1));
}
continue redo;
} else {
tmp.add(minSecond);
total = total + minSecond.price;
}
// 低价商品提前被消耗完，将最小的 高价格商品移除到低价格中
if (minList.size() == 0 && maxList.size() > 0) {
minList.add(0, maxList.remove(maxList.size() - 1));
continue redoLow;
}
}
Order order = new Order();
order.orderItems = tmp;
order.totalPrice = total;
order.sellerId = sellId;
orderList.add(order);
}
}
return orderList;
}
相关文章
