Teste mochila

novocatarata.cpp

#include <bits/stdc++.h>

using namespace std;
#define maxn 200010

vector <int> pesos,valores;

int c = 0;

int pd[1000100][200100];


int mocbin(int i,int p){
  ++c; 
  if(i<0){
    return 0;
  }

  if(pd[i][p]){
    return pd[i][p];
  }

  if(i==0){
    if(pesos[0] <= p)
      return pd[i][p] = valores[i];
    else
      return 0;
  }

  int cEle=0, sEle=0;
  if (pesos[i] <= p) {
      cEle = valores[i]+ mocbin(i-1, p-pesos[i]);
  }

  sEle=mocbin(i-1, p);

  // return max(sEle,cEle);
  return pd[i][p] = max(cEle,sEle);
}

int main()
{
    
	int W = 3,n; // TODO LER NÙMERO DE VISTAS
	
	cin >> n >> W;

	int wt[n];

	for (int i=0;i<n;i++) {
		cin >> wt[i]; 
		pesos.push_back(wt[i]);
		valores.push_back(1);
	}
	
	
	
	int max_valor = mocbin(n - 1, W);

	cout << max_valor << endl;

	return 0;
}