将n个数字划分为两个组的总和小于k

Question

有n个数字，范围为1-100。n范围为1-1000。

另一个数字k。它的边界是1＆lt; = k＆lt; = 10^6

如何检查是否可能将给定的n个数字划分为两组，以使两个组号的总和均为＆lt; = k。

我正在寻找高级实施方法或算法，如果可能的情况可能会返回true。

Answer 1

基于DP的解决方案，具有O（n*sum）

的复杂性

for (int i = 0; i < n; i++) {
    sum += a[i];
  }
  int[][] dp = new int[n + 1][sum + 1];
  for (int i = 0; i <= n; i++) {
    dp[i][0] = 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= sum; j++) {
      dp[i + 1][j] = dp[i][j];
      if (a[i] <= j) {
        dp[i + 1][j] |= dp[i][j - a[i]];
      }
    }
  }
  for (int i = sum / 2; i >= 0; i--) {
    if (dp[n][i] == 1) {
      int x = sum - i;
      if (x > k || i > k) {
        System.out.println("NO");
      } else {
        System.out.println("YES");
      }
      break;
    }
  }