Guest User

Untitled

a guest
Oct 5th, 2011
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stdlib.h>
  4. #include <vector>
  5.  
  6. #define EPS 1e-9
  7. #define INF 1e+9
  8.  
  9. using namespace std;
  10.  
  11. int main() {
  12.     freopen("input.txt","r",stdin);
  13.     freopen("output.txt","w",stdout);
  14.     int i,j,n,p,sum,m,r;
  15.     m = INF;
  16.     sum = 0;
  17.     cin>>n>>p;
  18.     vector <int> w (n+1,0);
  19.     for (i=1; i<=n; ++i) {
  20.         cin>>w[i];
  21.         sum+=w[i];
  22.     }
  23.     vector < vector <bool> > dp (n+1, vector <bool> (sum+1,false));
  24.     dp[0][0] = true;
  25.     for (i=1; i<=n; ++i) {
  26.         for (j=0; j<=sum; ++j) {
  27.             dp[i][j] = dp[i-1][j];
  28.             if (j-w[i] >= 0) dp[i][j] = dp[i][j] || dp[i-1][j-w[i]];
  29.         }
  30.     }
  31.     for (i=0; i<=sum; ++i) {
  32.         if (dp[n][i] && abs(i-p) < m) {
  33.             m = abs(i-p);
  34.             r = i;
  35.         }
  36.     }
  37.     cout<<r;
  38.     return 0;
  39. }
  40.  
  41.  
RAW Paste Data