Teilen von n Zahlen in zwei Gruppen, die jeweils eine Summe kleiner als gleich haben k

Question

Es gibt n Zahlen im Bereich von 1-100. n reicht von 1-1000.

Eine andere Nummer k. Seine Grenzen sind < 1 = k < = 10^6

Wie Wenn es möglich zu prüfen, die angegebenen Zahlen n in zwei Gruppen derart, daß die Summe der beiden Gruppennummern zu unterteilen ist < = k.

Ich bin auf der Suche nach einem High-Level-Implementierungsansatz oder einem Algorithmus, der wahr zurückgibt, wenn die Division möglich ist.

Answer 1

Ein DP-basierte Lösung mit einer Komplexität von O (n * Summe)

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