將n個數字分成兩組，每組的總和小於等於k

Question

有n個數字，範圍爲1-100。 n的範圍在1-1000之間。

另一個數字k。其邊界是1 < = K < = 10^6

如何檢查是否其可以分割給定的n箇中的兩組，使得兩個基團數目的總和是< = K。

我正在尋找一個高層次的實現方法或算法，如果可能的話將返回true。

Answer 1

一個DP基於與複雜度O（N *總和）

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