选择数组中最佳组合算法

发表于

问题

有 N 个等高不等长的长方形，排列成 2 行。求 2 行长度差值最小的情况下长那行的长度。例如 {2，2，3}，结果为 4。

[问题]

答案

计算出全部符合条件的组合数，再找出最大的组合数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class NChooseK {
  private static long findOptimum(List<Integer> numbers, long maxSum) {
    Set<Integer> sums = new HashSet<>(Collections.singletonList(0));
    numbers.forEach(number -> {
      Set<Integer> subSums = sums.stream().map(sum -> sum + number)
          .filter(newSum -> newSum <= maxSum).collect(toSet());
      sums.addAll(subSums);
    });
    return sums.stream().mapToLong(i -> i).max().orElse(0);
  }
  public static void main(String[] args) {
    List<Integer> numbers = Arrays.asList(3, 7, 7, 5, 4);
    long sum = numbers.stream().mapToLong(i -> i).sum();
    long mid = sum / 2;
    long optimum = findOptimum(numbers, mid);
    long answer = sum - optimum;
    System.out.println("Answer is " + answer);
  }
}