API tools faq
paste
S_Aditya

Rod Problem naive dp

S_Aditya
Mar 24th, 2021 (edited)
83
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 2004; //taken according to constraints
  5.  
  6. int main()                  
  7. {
  8.     int n; cin >> n;
  9.  
  10.     int a[n];
  11.  
  12.     for(int i = 0; i < n; i++)
  13.     cin >> a[i];
  14.  
  15.     int dp[n + 1][N][N]; memset(dp, 0, sizeof(dp));
  16.  
  17.     dp[0][0][0] = 1; //base case, no considerations, no elements in bags   
  18.  
  19.     for(int i = 0; i < n; i++)
  20.     {
  21.         for(int bag1 = 0; bag1 < N; bag1++)
  22.         {
  23.             for(int bag2 = 0; bag2 < N; bag2++)
  24.             {
  25.                 //skip this current rod
  26.                 dp[i + 1][bag1][bag2] |= dp[i][bag1][bag2];
  27.  
  28.                 //put rod in bag1
  29.                 if(bag1 + a[i] < N)
  30.                 dp[i + 1][bag1 + a[i]][bag2] |= dp[i][bag1][bag2];
  31.  
  32.  
  33.                 //put rod in bag2
  34.                 if(bag2 + a[i] < N)
  35.                 dp[i + 1][bag1][bag2 + a[i]] |= dp[i][bag1][bag2];
  36.             }
  37.         }
  38.     }
  39.  
  40.     int ans = 0;
  41.  
  42.     for(int i = 0; i < N; i++)
  43.     if(dp[n][i][i])
  44.     ans = max(ans, i);
  45.  
  46.     cout << ans;
  47.  
  48.     return 0;
  49. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!