亚马逊OA - 订单匹配问题

参考了下 “背包问题九讲”中的二维费用问题，这道题应该可以用三维费用DP来解吧。 F[i, x1, x2, x3] = max{}

您好！
本帖隐藏的内容需要积分高于 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

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

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

我在阿里也碰到一样的题目，本来以为和leetcode上面的那道shopping offers一样，没想到同样的套路根本行不通，也是不知道改怎么下手。

帮顶，期待大神解答。

另外，楼主，可否把英文版本的题目发一下？

求人不如求己...已经搞定了，用的是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. }

复制代码

可以說明一下思路嗎

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

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

wsx247 发表于 2018-3-15 01:54
可以說明一下思路嗎

DFS，每个位置上都遍历整个comb的HashMap，直到有商品数量越界。