# Cod sursa(job #1606700)

Utilizator Data 20 februarie 2016 14:28:16 Problema rucsacului 100 cpp done Arhiva educationala 0.95 kb
``````#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
//#include <queue>
#include <algorithm>

using namespace std;
const int nmax = 10001;
int n,gmax;
int g[nmax];
vector<pair<int, int>> w;

bool mysort(const pair<int, int> &a, const pair<int, int> &b) { return a.first < b.first; }
inline int max(const int a, const int b) { return a > b ? a : b; }

int main(){
freopen("rucsac.in", "r", stdin);
freopen("rucsac.out", "w", stdout);
scanf("%d %d", &n, &gmax);
int a, b;
for (int i = 0; i < n; i++) {
scanf("%d %d", &a, &b);
w.push_back(make_pair(a, b));					// first = weight second = value
}

sort(w.begin(), w.end(), mysort);

memset(g, 0, sizeof(g));

for (int i = 0; i < w.size(); i++)						// fiecare obiect
for (int j = gmax; j >= 0; j--)
if (w[i].first <= j)
g[j] = max(g[j], g[j - w[i].first] + w[i].second);

printf("%d ", g[gmax]);
fclose(stdin);
fclose(stdout);
return 0;
}``````