Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Código exemplo Memoization - Programação Dinâmica - DojoRio
#include <iostream>
#include <cstring>
#define MAX 1000
using namespace std;
//Testar com 5 10 /n 1 2 3 4 5 e 5 10 /n 3 3 3 3 3
int W[MAX];
bool V[MAX][MAX];
bool M[MAX][MAX];
bool K(int n, int w) {
if (w==0) return true;
if (w<0 || n==0) return false;
if(V[n][w]){
return M[n][w];
}else{
V[n][w] = true;
return M[n][w] = K(n-1, w) || K(n-1, w-W[n-1]);
}
}
int main() {
int n, w;
while(cin >> n >> w) {
memset(V, false, sizeof(V));
for(int i=0; i<n; i++)
cin >> W[i];
cout << K(n, w);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.