循环所有可能的组组合以获得最大值

Question

我正在组装一个java小程序，使任务在工作中更快、更高效。

用户定义项目列表需要拆分成的三个组的大小。列表中的每个项目根据它被放入三个组中的哪个组具有不同的值。小程序需要显示哪个组合的总价值最高。

示例：带有列的二维整数数组；项目编号、第1组中的值、第2组中的值和第3组中的值。

16   2   2   5
19   6   0   3
24   1   4   4
25   4   2   3
27   4   2   3
29   3   3   3
31   5   3   1
32   5   2   2

这样，用户定义组1有3个插槽，组2有3个插槽，组3有2个插槽。

小程序应不按特定顺序显示以下解决方案

Group 1: 19, 31, 32
Group 2: 24, 27, 29
Group 3: 16, 25
OR
Group 1: 19, 27, 32
Group 2: 24, 29, 31
Group 3: 16, 25
OR
Group 1: 19, 31, 32
Group 2: 24, 25, 29
Group 3: 16, 27
OR
Group 1: 19, 25, 32
Group 2: 24, 29, 31
Group 3: 16, 27

我可以管理一种效率不太高的方法来运行阵列，尽管所有可能的订单都是如此，但它会产生重复的解决方案（即16,25和25,16）。我相信有一种方法可以总结出所有可能的组合，甚至不用洗牌数组。我只是一时想不起来。如果你们中有人有这样的方法，我将不胜感激。

Answer 1

更新：使用动态规划的新方法

（旧的：）

我认为我们可以使用贪婪的方法。这个想法是：

1. 查找表中的最大值。将相应的项目放入相应的组中
2. 从表中删除项目的对应行
3. 当组已满时，删除该组的相应列

为了实现上述想法，我们可以使用一个数组使用[]来识别一个项目是否被使用（已经放入一个组），三个最大堆来表示表中的三个值列。堆元素就像（value是key）。假设三个堆是H[0]、H[1]和H[2]。算法是这样的：

Init bool array `used[n]` to all false 
Init heap array `H[3]`
Init int array `capacity[3]` to required group sizes
for(int i from 0 to n-1){
    int v = -1, heap_number, item_number;
    for(int j from 0 to 2){
        if(capacity[j] == 0){
            continue;
        }
        while(used[H[j].top().item_number]){
            H[j].pop();
        }
        if(H[j].top().value > v){
            v = H[j].top().value;
            heap_number = j;
            item_number = H[j].top().item_number;
        }
    }
    Assign Item item_number to Group heap_number
    used[item_number] = true;
    capacity[heap_number]--;
}

这是我的新方法，一种动态编程方法：

• 假设f[i][j][k]表示组1、2和3的解，每个组分别剩余i、j和k个时隙。解决方案是三个列表，记录从项目到组的分配。假设a=i j k

Answer 2

我想不出一个解决方案，但回答你的问题——关于遍历所有可能的和——你可以使用递归。

// @row - currently processed row
// @g1, g2, g3 - arrays with numbers of rows put in respective group
// @options - for results
// @rows - source array
void PROCESS_ROW(int row, int[] g1, int[] g2, int[] g3, int[][][][] options, rows) {
    if (row >= rows.length) {
        // Recursion ended, collecting generated distribution
        options[].push_back(new int[3][][]);
        options[last][0] = g1.clone();
        options[last][1] = g2.clone();
        options[last][2] = g3.clone();
        return;
    }
    // Trying to put row in each group consequently
    if (g1.length < g1_slots) {
        g1.push_back(row);
          PROCESS_ROW(row + 1, g1, g2, g3, options, rows);
        g1.pop_back();
    }
    if (g2.length < g2_slots) {
        g2.push_back(row);
          PROCESS_ROW(row + 1, g1, g2, g3, options, rows);
        g2.pop_back();
    }
    if (g3.length < g3_slots) {
        g3.push_back(row);
          PROCESS_ROW(row + 1, g1, g2, g3, options, rows);
        g3.pop_back();
    }
}

int[][] rows;
// .. fill
int[][][][] options;

PROCESS_ROW(0, new int[], new int[], new int[], options, rows);
// now options contains all possible groupings

实际上，这段代码不是Java，所以需要进行修改。此外，g1_插槽等也必须作为参数传递给函数，但这只是细节。这个想法是可以理解的。此外，很可能在第一个if部分中包含更强的处理，计算总和并存储最高值以及可能的组合。并在每次遇到更高的和时清除数组<当然，这个解决方案意味着行有数字0，1，2..，除了16，19，25…所以，这个方面应该再次调整，使用映射行而不是数组。但正如我所说，这是细节。