4

我正在整理一个 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）。我确信有一种方法可以总结所有可能的组合，而无需重新排列数组。此刻，我实在无法理解它。如果你们中的任何人有这种方法，我将不胜感激。

4

2 回答 2

0

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

（旧的：）

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

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

为了实现上面的想法，我们可以使用一个数组used[]来识别是否使用了一个项目（已经放入一个组中），三个最大堆来表示表中的三个值列。堆元素就像（值是键）。假设三个堆是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。
  • 状态转移方程：f[i][j][k] = max{f[i-1][j][k] + Item[a].value_1, f[i][j-1][k] + Item[a].value_2, f[i][j][k-1] + Item[a].value_3}。
  • 初始状态：f[0][0][0] = 0。
  • 最终答案：f[group_1_size][group_2_size][group_3_size]。
于 2013-11-09T21:32:31.947 回答
0

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

// @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_slots 等也必须作为参数传递给函数，但它是细节。这个想法是可以理解的。此外，很可能在第一if部分中包含更强的处理，计算总和并将最高的值与可能的组合一起存储。并且每次遇到更高的总和时清除数组。
当然，这个解决方案意味着行的数字是 0、1、2..，而不是 16、19、25......所以，这个方面应该再次调整，使用Map rows而不是数组。但正如我所说，这是细节。

于 2013-11-09T22:39:24.670 回答