ejemplo de código de programación dinámica del algoritmo de mochila

Si hallas algún fallo con tu código o trabajo, recuerda probar siempre en un entorno de testing antes aplicar el código al trabajo final.

Ejemplo: mochila

#includeusingnamespace std;
vector<pair<int,int>>a;//dp table is full of zerosint n,s,dp[1002][1002];voidini()for(int i=0;i<1002;i++)for(int j=0;j<1002;j++)
            dp[i][j]=-1;intf(int x,int b)//base solutionif(x>=n or b<=0)return0;//if we calculate this before, we just return the answer (value diferente of 0)if(dp[x][b]!=-1)return dp[x][b];//calculate de answer for x (position) and b(empty space in knapsack)//we get max between take it or not and element, this gonna calculate all the//posible combinations, with dp we won't calculate what is already calculated.return dp[x][b]=max(f(x+1,b),b-a[x].second>=0?f(x+1,b-a[x].second)+a[x].first:INT_MIN);intmain()//fast scan and print
	ios_base::sync_with_stdio(0);cin.tie(0);//we obtain quantity of elements and size of knapsack
	cin>>n>>s;
	a.resize(n);//we get value of elementsfor(int i=0;i<n;i++)
		cin>>a[i].first;//we get size of elementsfor(int i=0;i<n;i++)
		cin>>a[i].second;//initialize dp tableini();//print answer
	cout<<f(0,s);return0;

Recuerda algo, que te brindamos la opción de añadir una evaluación si diste con la solución.

---

---

Utiliza Nuestro Buscador