Cod sursa(job #2729848)
Utilizator | isache bogdan bogdan62003 | Data | 25 martie 2021 15:00:55 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <bits/stdc++.h>
using namespace std;
int n, w[1001], p[1001], dp[1001][10001], G, aux;
int main()
{
cin>>n>>G;
for(int i=1;i<=n;i++)
cin>>w[i]>>p[i];
for(int i=1;i<=n;i++)
for(int g=1;g<=G;g++)
{
dp[i][g]=dp[i-1][g]; ///nu iau obiectul i
if(g>=w[i]) ///incerc sa iau obiectul
{
aux=dp[i-1][g-w[i]]+p[i];
if(aux>dp[i][g])
dp[i][g]=aux;
}
}
cout<<dp[n][G];
}