Cod sursa(job #3176258)
Utilizator | Data | 26 noiembrie 2023 21:53:35 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
using namespace std;
ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");
const int dim = 10001;
int dp[dim];
int main()
{
int N, capacitate;
cin >> N >> capacitate;
int val[N + 1], greutate[N + 1], i, j;
for(i = 1; i <= N; i++)
cin >> greutate[i] >> val[i];
for(i = 1; i <= N; i++)
for(j = capacitate - greutate[i]; j >= 0; j--)
dp[j + greutate[i]] = max(dp[j + greutate[i]], dp[j] + val[i]);
cout << dp[capacitate];
return 0;
}