Advertisement
Oppenheimer

Subset sum exists or not

Aug 14th, 2022
28
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. // check whether the given subset sum is possible or not.
  2. // here we dont have wt array
  3.  
  4. int solve(vector<int> value , int knapsack){
  5.     int  n = value.size();
  6.     int sum=0;
  7.     for(int a=0;a<n;a++)sum+=value[a];
  8.    
  9.     vector<vector<bool>> dp (n+1 ,vector<bool>(sum+1,false));
  10.     // a represents the ath element .. b represents the knapsack present
  11.    
  12.     for(int a=0;a<=n;a++)dp[a][0] = true;// sum 0 is possible even if do not select anything
  13.    
  14.     for(int a=1;a<=n;a++){
  15.         for(int b=1;b<=sum;b++){
  16.             if(value[a-1]<=b){
  17.             dp[a][b] = dp[a-1][b-value[a-1]] || dp[a-1][b]; //either i choose the ath element or not
  18.             }else{
  19.             dp[a][b] = dp[a-1][b]; // cant choose the ath element becuase its weight is more
  20.             }
  21.         }
  22.     }
  23.     return dp[n][knapsack];
  24.  
  25. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement