Cod sursa(job #2693700)
Utilizator | Data | 6 ianuarie 2021 19:17:18 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <fstream>
#include<iostream>
#include <vector>
using namespace std;
ifstream be("rucsac.in");
ofstream ki("rucsac.out");
int main()
{
int n,g;
be>>n>>g;
vector<int>w(n+1);
vector<int>p(n+1);
for(int i=1;i<=n;i++)
{
be>>w[i]>>p[i];
}
//vector<vector<int> >d(n+1,vector<int>(g+1,0));
vector<int>d(g+1,0);
for(int i=1;i<=n;i++)
{
for(int cw=g;cw>=w[i];cw--)
{
d[cw]=max(d[cw],d[cw-w[i]]+p[i]);
}
}
ki<<d[g]<<endl;
return 0;
}