
/**
我写了一半的代码,不知如何继续下去,求大佬
public class Ball { private Color color; private Meterial meterial; private int weight; } public enum Color { YELLOW("YELLOW","黄色"), ORANGE("ORANGE","橙色"), RED("RED","红色"), BLUE("BLUE","蓝色"); } public enum Meterial { IRON("IRON","铁"), WOOD("WOOD","木"), GLASS("GLASS","玻璃"); } public void calculate(Ball[] balls) { int totalWeight = 0; List<Ball> red = new ArrayList<>(); List<Ball> orange = new ArrayList<>(); List<Ball> yellow = new ArrayList<>(); List<Ball> blue = new ArrayList<>(); List<Ball> iron = new ArrayList<>(); List<Ball> wood = new ArrayList<>(); List<Ball> glass = new ArrayList<>(); HashMap<String,List<Ball>> basketsMap = new HashMap(); basketsMap.put(Color.RED.getKey(),red); basketsMap.put(Color.ORANGE.getKey(),orange); basketsMap.put(Color.YELLOW.getKey(),yellow); basketsMap.put(Color.BLUE.getKey(),blue); basketsMap.put(Meterial.IRON.getKey(),iron); basketsMap.put(Meterial.WOOD.getKey(),wood); basketsMap.put(Meterial.GLASS.getKey(),glass); for (int i=0; i<balls.length; i++) { if (basketsMap.containsKey(balls[i].getColor().getKey())) { List<Ball> color = basketsMap.get(balls[i].getColor().getKey()); if (color.size()<3) { color.add(balls[i]); totalWeight+=balls[i].getWeight(); } else { System.out.println(basketsMap.get(balls[i].getColor().getKey()).toArray().toString()); basketsMap.remove(balls[i].getColor().getKey()); } } if (basketsMap.containsKey(balls[i].getMeterial().getKey())) { List<Ball> material = basketsMap.get(balls[i].getMeterial().getKey()); if (material.size()<3) { material.add(balls[i]); totalWeight+=balls[i].getWeight(); } else { System.out.println(basketsMap.get(balls[i].getMeterial().getKey()).toArray().toString()); basketsMap.remove(balls[i].getColor().getKey()); } } } 1 w0000 2018-09-14 14:35:32 +08:00 这个题目是不是没描述完整? 表示这个球筐里对球的限定 是什么意思?限定的是个数? |
2 Breadykid OP @w0000 意思是:7 个球筐上依次写着[红球,橙球,黄球,蓝球,铁球,木球,玻璃球],表示这个球筐里对球的限定,就是写着红球的框里可以放有“红色”属性的球的意思,可以放红木球,红铁球,红玻璃球,这样 |
3 bzw875 2018-09-14 15:04:50 +08:00 请问组成最大重量的 N 个球筐限定的组合是什么? 这句话什么意思啊,7*3=21,每个框都有球啊,不能不放 |
6 cigarzh 2018-09-14 15:08:11 +08:00 via iPhone 背包问题加了点限定? |
7 maichael 2018-09-14 15:18:16 +08:00 说个最简单的思路,一个个球遍历,先找到那个框可以存放这个球,再判断这个框什么已经满了,如果满了再判断这个球是否比这个框里面三个都要轻,如果都要轻就找有没另一个框可以换。被替换下来的球重新进入队列。 |
11 Deville 2018-09-14 15:30:38 +08:00 咦,这道题,似曾相识 |
12 uleh 2018-09-14 16:06:19 +08:00 lz 你的题目归结一下就是下面这个二位数组。 算最重的时候,就按给定的框遍历一下可能的取值,把最大的取出来就行了。 例如给 N=2 (红球框,铁球框),就是下面这个矩阵 X[红]遍历一下最大的 3 个(26,36,3),然后 X[铁]遍历剩下最大的 3 个 |红 |橙|黄|蓝| ------------------ 铁 |15,26|... ------------------ 木 |31,36|... ------------------ 玻璃 |3 |... |
13 Breadykid OP 我最后的实现哇,如果求得是这个意思得话 public void calculate(Ball[] balls) { final String[] colorType = {Color.RED.getKey(),Color.ORANGE.getKey(),Color.YELLOW.getKey(),Color.BLUE.getKey()}; final String[] materialType = {Meterial.IRON.getKey(),Meterial.WOOD.getKey(),Meterial.GLASS.getKey()}; // 质量排序 for (int i = 0; i < balls.length; i++) { for (int j = 1; j < balls.length; j++) { int a = balls[i].getWeight(); int b = balls[j].getWeight(); if (i<j && a<b) { Ball temp = balls[i]; balls[i] = balls[j]; balls[j] = temp; } } } // color for (int n=0; n<colorType.length; n++) { int totalWeight = 0; final int count = 3; List<Ball> color = new ArrayList<>(); for (int i=0; i<balls.length; i++) { if (colorType[n].equals(balls[i].getColor().getKey())) { if (color.size()<count) { System.out.println(balls[i].toString()); color.add(balls[i]); totalWeight+=balls[i].getWeight(); } } } System.out.println(String.format("%s 总质量 %s",colorType[n],totalWeight)); } // material for (int n=0; n<materialType.length; n++) { int totalWeight = 0; final int count = 3; List<Ball> material = new ArrayList<>(); for (int i=0; i<balls.length; i++) { if (materialType[n].equals(balls[i].getMeterial().getKey())) { if (material.size()<count) { System.out.println(balls[i].toString()); material.add(balls[i]); totalWeight+=balls[i].getWeight(); } } } System.out.println(String.format("%s 总质量 %s",materialType[n],totalWeight)); } } |
14 uleh 2018-09-14 16:07:51 +08:00 #12 修改一下说法,不是二维数组,算是个矩阵。因为你这个球之间其实没有交叉,比传统的背包问题其实还简单些。 |
16 xiaoxinxiaobai 2018-09-14 16:57:18 +08:00 via Android 题都读不懂。。。 |