Pagini recente » Cod sursa (job #1047810) | Cod sursa (job #1673732)
#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <map>
using namespace std;
vector<pair<int, int> > Ob;
int nrO, G, a, b, pMax;
void RucsacNxG ();
void RucsacHash ();
void Read ();
int main()
{
Read();
//RucsacNxG();
RucsacHash();
}
void RucsacHash()
{
map<int, int> M, M2;
M2.insert(make_pair(0, 0));
int Solution = -((1<<31)-1);
for(int i = 1; i <= nrO; ++i)
{
for(map<int, int>::iterator it = M2.begin(); it != M2.end(); ++it)
{
int newG = it->first + Ob[i].first;
if(newG <= G) { // Adauga un nou obiect
int newProfit = it->second + Ob[i].second;
map<int, int>::iterator newEl = M2.find(newG);
if(newEl == M2.end())
M.insert(make_pair(newG, newProfit));
else
M.insert(make_pair(newG, max(newProfit, newEl->second)));
}
// Pastreaza valoarile pentru greutatile deja calculate
map<int, int>::iterator originalEl = M.find(it->first);
if(originalEl != M.end())
M[originalEl->first] = max(it->second, originalEl->second);
else
M[it->first] = max(it->second, originalEl->second);
}
M2.erase(M2.begin(), M2.end());
M2.insert(M.begin(), M.end());
M.erase(M.begin(), M.end());
}
for(map<int, int>::iterator it = M2.begin(); it != M2.end() && it->first <= G; ++it)
Solution = max(Solution, it->second);
cout<<Solution<<'\n';
}
void RucsacNxG()
{
vector<int>D(G+1);
for(int o=1; o<=nrO; ++o)
for( int g=G; g>=0; --g)
if(Ob[o].first <= g)
D[g] = max(D[g], (D[g - Ob[o].first] + Ob[o].second) );
for(int i=0; i<=G; ++i)
pMax = max(pMax, D[i]);
cout<<pMax<<'\n';
}
void Read ()
{
freopen("rucsac.in", "rt", stdin);
freopen("rucsac.out", "wt", stdout);
scanf("%d%d", &nrO, &G);
Ob.push_back(make_pair(0, 0));
for(int i=1; i<=nrO; ++i){
scanf("%d%d", &a, &b);
Ob.push_back(make_pair(a, b));
}
}