Cod sursa(job #2717266)

Utilizator Maria23Dutu Maria Maria23 Data 6 martie 2021 21:57:10
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> dp(10000, 0);

int main() {
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

   int nrObiecte, greutateMax;
   assert(fin>>nrObiecte>>greutateMax);

   for(int j = 0; j < nrObiecte; j ++) {
       int w, p;
       fin >> w >> p;
       for (int i = greutateMax; i >= 0; i--) {

           if (i + w <= greutateMax)
               dp[i + w] = max(dp[i + w], dp[i] + p);
       }
   }
//   for(int i : dp)
//       cout<<i<<"  ";
   fout<<*max_element(dp.begin(), dp.end());
   return 0;
}