Check if all people can vote on two machines | Java program to check if all people can vote using two machines within limited time ; Returns true if n people can vote using two machines in x time . ; dp [ i ] [ j ] stores maximum possible number of people among arr [ 0. . i - 1 ] can vote in j time . ; Find sum of all times ; Fill dp [ ] [ ] in bottom up manner ( Similar to knapsack ) . ; If remaining people can go to other machine . ; Driver code
public class Main { static boolean canVote ( int [ ] a , int n , int x ) { int [ ] [ ] dp = new int [ n + 1 ] [ x + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < x + 1 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += a [ i ] ; for ( int i = 1 ; i < n ; i ++ ) for ( int j = 1 ; j <= x ; j ++ ) if ( a [ i ] <= j ) dp [ i ] [ j ] = Math . max ( dp [ i - 1 ] [ j ] , a [ i ] + dp [ i - 1 ] [ j - a [ i ] ] ) ; else dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; return ( sum - dp [ n ] [ x ] >= x ) ; } public static void main ( String [ ] args ) { int n = 3 , x = 4 ; int [ ] a = { 2 , 4 , 2 } ; if ( canVote ( a , n , x ) ) { System . out . println ( " YES " ) ; } else { System . out . println ( " NO " ) ; } } }