Código exemplo Memoization - Programação Dinâmica - DojoRio

memoization_example.cpp

#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);    
    }
}