亚马逊OA - 订单匹配问题

刚刚做完的OA，自己做得非常不好，想问问大家的想法。

给定一个订单order数组，代表对应商品的数量，比如{2, 3, 1}代表ABC商品各有2，3，1个。

另外给定一个HashMap，这个map的value是这几种商品的组合，比如{2, 1, 1},

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这需要确保其他商品的数量不超过order中的数量，想来想去，不是一个好方法。

请问大家有什么思路吗？

谢谢！

我靠LZ怎么拿到oa的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求人不如求己...已经搞定了，用的是backtracking，之前想复杂了

1. /*
   
2. 一个淘宝的订单中包含n(10>=n>=1)种商品A1，A2，...，An，每种商品数量分别为a1，a2，...，an个，记做{a1,a2,...,an}(ak>0)。
   
3. 
   
4. 订单在仓库生产过程中，仓库为了提升作业效率，会提前对热门组合商品进行预包装。
   
5. 假设这n个商品有m(9>=m>=1)个商品组合，每个组合bomk包含A1，A2，...，An的数量分别为{b1,b2,...,bn}(bk>=0,至少存在一个bk>0)
   
6. 
   
7. 
   
8. 
   
9. 举例如下：
   
10. 
    
11. 订单包含A，B，C商品，数量为{2，3，1}，商品组合bom1{2，1，1}，bom2{1，1，0}，bom3{0，1，1}
    
12. 
    
13. 
    
14. 
    
15. 对以上订单匹配给定商品组合，得到的可能匹配结果为：res1.匹配到组合1一套，剩余B商品；res2.匹配到组合2两套，组合3一套，不剩商品；
    
16. 
    
17. 现要求订单的最优匹配，最优匹配的原则为：1.匹配组合后，剩余商品种类数越少越好；2.在剩余商品种类数相同的情况下，匹配到的组合种类数越少越好；
    
18. 
    
19. 例如上面例子，我们认为res2优于res1。
    
20. 
    
21. 
    
22. 
    
23. 现需要编写程序，输入格式为：
    
24. 
    
25. n,m
    
26. 
    
27. a1,a2,...,an
    
28. 
    
29. bom1,b11,b12,...,b1n
    
30. 
    
31. bom2,b21,b22,...,b2n
    
32. 
    
33. ....
    
34. 
    
35. bomm,bm1,bm2,...,bmn
    
36. 
    
37. 
    
38. 
    
39. 输入数据的格式说明（数据间使用英文逗号分隔）：
    
40. 
    
41. 第一行数据：n个商品，m个预包方案
    
42. 
    
43. 第二行数据：商品1个数，商品2个数，。。。，商品n个数
    
44. 
    
45. 第三行数据：bom1，商品1个数，商品2个数，。。。，商品n个数
    
46. 
    
47. 第n-1行数据：。。。。
    
48. 
    
49. 第n行数据：bomn，商品1个数，商品2个数，。。。，商品n个数
    
50. 
    
51. 
    
52. 
    
53. 针对输入数据找出最优匹配，输出最优匹配的组合及套数，比如针对上面的例子输出：
    
54. 
    
55. match result:
    
56. 
    
57. bom2*2，bom3*1
    
58. 
    
59. 注：输出结果有多个时可以乱序
    
60. */
    
61. 
    
62. import java.util.ArrayList;
    
63. import java.util.HashMap;
    
64. import java.util.List;
    
65. import java.util.Map;
    
66. import java.util.Scanner;
    
67. 
    
68. public class Main {
    
69.     /** 请完成下面这个函数，实现题目要求的功能 **/
    
70.     /** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^  **/
    
71.     private static Map<String, Integer> optimalCombos;
    
72.     private static Map<String, Integer> currentCombos;
    
73.     private static int minLeftKinds = Integer.MAX_VALUE;
    
74. 
    
75.     public static void main(String[] args) {
    
76. 
    
77.         List<Integer> order = new ArrayList<Integer>();
    
78.         Map<String, List<Integer>> boms = new HashMap<String, List<Integer>>();
    
79. 
    
80.         Scanner in = new Scanner(System.in);
    
81.         String line = in.nextLine();
    
82. 
    
83.         Integer n = Integer.parseInt(line.split(",")[0]);
    
84.         Integer m = Integer.parseInt(line.split(",")[1]);
    
85. 
    
86.         line = in.nextLine();
    
87.         String[] itemCnt = line.split(",");
    
88.         for(int i = 0; i < n ; i++){
    
89.             order.add(Integer.parseInt(itemCnt[i]));
    
90.         }
    
91. 
    
92.         for(int i = 0; i < m; i++){
    
93.             line = in.nextLine();
    
94.             String[] bomInput = line.split(",");
    
95.             List<Integer> bomDetail = new ArrayList<Integer>();
    
96. 
    
97.             for(int j = 1; j <= n; j++ ){
    
98.                 bomDetail.add(Integer.parseInt(bomInput[j]));
    
99.             }
    
100.             boms.put(bomInput[0], bomDetail);
     
101.         }
     
102.         in.close();
     
103. 
     
104.         Map<String, Integer> res = resolve(order, boms);
     
105. 
     
106.         System.out.println("match result:");
     
107.         for(String key : res.keySet()){
     
108.             System.out.println(key+"*"+res.get(key));
     
109.         }
     
110.     }
     
111. 
     
112.     // write your code here
     
113.     public static Map<String, Integer> resolve(List<Integer> order, Map<String, List<Integer>> boms) {
     
114.         optimalCombos = new HashMap<>();
     
115.         currentCombos = new HashMap<>();
     
116.         minLeftKinds = Integer.MAX_VALUE;
     
117. 
     
118.         return resolve(order, boms, 1);
     
119.     }
     
120. 
     
121.     private static Map<String, Integer> resolve(List<Integer> order, Map<String, List<Integer>> boms, int depth) {
     
122.         for (int i = 1; i <= boms.size(); i++) {
     
123. //            System.out.println("depth = "+ depth);
     
124. //            System.out.println("i = " + i);
     
125. //            System.out.println("minLeftKinds = " + minLeftKinds);
     
126. //            System.out.println("currentCombos:" + currentCombos);
     
127. //            System.out.println("optimalCombos:" + optimalCombos);
     
128. //            System.out.println("-------------------------------");
     
129. 
     
130.             List<Integer> combo = boms.get("bom" + i);
     
131.             if (isValidCombo(order, combo)) {
     
132.                 deductCombo(order, combo);
     
133.                 currentCombos.put("bom" + i, currentCombos.getOrDefault("bom" + i, 0) + 1);
     
134. 
     
135.                 resolve(order, boms, depth + 1);
     
136. 
     
137.                 addCombo(order, combo);
     
138.                 currentCombos.put("bom" + i, currentCombos.get("bom" + i) - 1);
     
139.             } else {
     
140.                 int leftKinds = kindOfItemsInList(order);
     
141.                 if (leftKinds < minLeftKinds) {
     
142.                     minLeftKinds = leftKinds;
     
143.                     optimalCombos = new HashMap<>(currentCombos);
     
144.                 } else if (leftKinds == minLeftKinds) {
     
145.                     if (kindOfCombos(currentCombos) < kindOfCombos(optimalCombos)) {
     
146.                         optimalCombos = new HashMap<>(currentCombos);
     
147.                     }
     
148.                 }
     
149.             }
     
150.         }
     
151. 
     
152.         return optimalCombos;
     
153.     }
     
154. 
     
155.     public static int kindOfItemsInList(List<Integer> list) {
     
156.         int count = 0;
     
157.         for(int i = 0; i < list.size(); i++) {
     
158.             if (list.get(i) > 0) {
     
159.                 count++;
     
160.             }
     
161.         }
     
162.         return count;
     
163.     }
     
164. 
     
165.     public static boolean isValidCombo(List<Integer> items, List<Integer> combo) {
     
166.         for (int i = 0; i < combo.size(); i++) {
     
167.             if (items.get(i) < combo.get(i)) {
     
168.                 return false;
     
169.             }
     
170.         }
     
171.         return true;
     
172.     }
     
173. 
     
174.     public static void deductCombo(List<Integer> items, List<Integer> combo) {
     
175.         for (int i = 0; i < combo.size(); i++) {
     
176.             items.set(i, items.get(i) - combo.get(i));
     
177.         }
     
178.     }
     
179. 
     
180.     public static void addCombo(List<Integer> items, List<Integer> combo) {
     
181.         for (int i = 0; i < combo.size(); i++) {
     
182.             items.set(i, items.get(i) + combo.get(i));
     
183.         }
     
184.     }
     
185. 
     
186.     public static int kindOfCombos(Map<String, Integer> combos) {
     
187.         int count = 0;
     
188.         for(int i = 1; i <= combos.size(); i++) {
     
189.             if (combos.getOrDefault("bom" + i, 0) != 0) {
     
190.                 count++;
     
191.             }
     
192.         }
     
193.         return count;
     
194.     }
     
195. }

复制代码

Backtracking？
新建一个class，里面存{{#C1,#C2,#C3},剩余数量{#A,#B,#C}},
C1,C2,C3依次尝试，试过C3后将答案存在PriorityQueue里，Key的话先比(#A+#B+#C)谁小，相同的话比{#C1,#C2,#C3}谁的0多

这个看起来像是 社招的OA啊 楼主投的是实习吗？

这一道典型的中等难度的dfs的问题，楼主在lintcode上搜一下ship orders相关的

czcbangkai 发表于 2018-3-10 19:14
我靠LZ怎么拿到oa的

找人组内内推的，等了很久：（

cheese_harry 发表于 2018-3-10 20:19
这个看起来像是 社招的OA啊 楼主投的是实习吗？

确实申请的是实习

wy3148 发表于 2018-3-11 06:56
这一道典型的中等难度的dfs的问题，楼主在lintcode上搜一下ship orders相关的

不好意思，我没有在Lintcode找到相关的题。你能提供一下题号，或者题目名称吗？谢谢

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies