n個の数値を合計がk未満の2つのグループに分割する

Question

n個の数値があり、1〜100の範囲です。 nは1〜1000の範囲である。

別の番号k。その範囲は、< = k < = 10^6 である。両方のグループ番号の合計が< = kとなるように、与えられたn個の数値を2つのセットに分けることができるかどうかをチェックする方法。

私は高度な実装方法、または分割が可能な場合にtrueを返すアルゴリズムを探しています。

Answer 1

A Oの複雑さ（N *合計）とDPベースのソリューション

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