Skip to content

Instantly share code, notes, and snippets.

@JacAbreu
Created April 8, 2013 00:09
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save JacAbreu/5333223 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <cstring>
#define MAX 1000
using namespace std;
int W[MAX];
bool M[MAX][MAX];
int main() {
int n, w;
while(cin >> n >> w) {
for(int i=0; i<n; i++)
cin >> W[i];
for(int j=0; j<=w; j++)
M[0][j] = false;
for(int i=0; i<=n; i++)
M[i][0] = true;
for(int i=1; i<=n; i++) {
for(int j=1; j<=w; j++) {
M[i][j] = M[i-1][j] || M[i-1][j-W[i-1]];
}
}
cout << M[n][w] << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment