CTO 让我们老人做做公司现在招聘的面试题，一个二维数组的题目， orz

[Breadykid]

/**

• 有若 7 个球框，每个球筐最多能放 3 个球，可以不放球。
• 7 个球筐上依次写着[红球，橙球，黄球，蓝球，铁球，木球，玻璃球]，
• 表示这个球筐里对球的限定。现在有 20 个球，
• 规格如下：
• 红铁球 15g，红铁球 26g，
• 橙铁球 25g，
• 黄铁球 18g，黄铁球 13g，
• 蓝铁球 33g,
• 红木球 31g，红木球 36g，
• 橙木球 11g，橙木球 25g，
• 黄木球 7g，黄木球 18g，
• 蓝木球 10g，
• 红玻璃球 3g，
• 橙玻璃球 21g，橙玻璃球 16g，
• 黄玻璃球 45g，黄玻璃球 29g，
• 蓝玻璃球 3g，蓝玻璃球 7g
• 请问组成最大重量的 N 个球筐限定的组合是什么？
• 请写出伪代码。 */

我写了一半的代码，不知如何继续下去，求大佬

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());
            }
        }
    }

[w0000]

这个题目是不是没描述完整？ 表示这个球筐里对球的限定 是什么意思？限定的是个数？

[Breadykid]

@w0000 意思是：7 个球筐上依次写着[红球，橙球，黄球，蓝球，铁球，木球，玻璃球]，表示这个球筐里对球的限定，就是写着红球的框里可以放有“红色”属性的球的意思，可以放红木球，红铁球，红玻璃球，这样

[bzw875]

请问组成最大重量的 N 个球筐限定的组合是什么？
这句话什么意思啊，7*3=21，每个框都有球啊，不能不放

[maichael]

@bzw875 不需要把所有球都放进去的意思。

[maichael]

@w0000 限定的是比如“红球”就只能放红球或者红玻璃球之类的。

[cigarzh]

背包问题加了点限定？

[maichael]

说个最简单的思路，一个个球遍历，先找到那个框可以存放这个球，再判断这个框什么已经满了，如果满了再判断这个球是否比这个框里面三个都要轻，如果都要轻就找有没另一个框可以换。被替换下来的球重新进入队列。

[Breadykid]

@maichael 昂，我试下

[Breadykid]

@cigarzh 确实像背包问题，但我不知道怎么搞

[maichael]

@Breadykid 如果球先根据重量做一次排序的话，应该效率会高点。

[Deville]

咦，这道题，似曾相识

[uleh]

lz 你的题目归结一下就是下面这个二位数组。
算最重的时候，就按给定的框遍历一下可能的取值，把最大的取出来就行了。
例如给 N=2 （红球框，铁球框），就是下面这个矩阵 X[红]遍历一下最大的 3 个(26,36,3)，然后 X[铁]遍历剩下最大的 3 个

|红 |橙|黄|蓝|
------------------
铁 |15,26|...
------------------
木 |31,36|...
------------------
玻璃 |3 |...

[Breadykid]

我最后的实现哇，如果求得是这个意思得话


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));
}
}

[uleh]

#12 修改一下说法，不是二维数组，算是个矩阵。因为你这个球之间其实没有交叉，比传统的背包问题其实还简单些。

[Breadykid]

@uleh 有道理昂

[xiaoxinxiaobai]

题都读不懂。。。