Pagini recente » Cod sursa (job #285304) | Cod sursa (job #2534399) | Cod sursa (job #2097837) | Cod sursa (job #1741613) | Cod sursa (job #2957152)
#include<string.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 5001
int W[maxn], P[maxn];
int k = 0;
void init(int bt[]) {
if (k==0) {
bt[k] = -1;
} else {
bt[k] = bt[k-1];
}
}
int succesor(int bt[], int n) {
if (bt[k] == n - 1) return 0;
bt[k]++;
return 1;
}
int valid(int bt[], int wt[], int W) {
int s = 0;
for (int i = 0; i <= k; i++) {
s += wt[bt[i]];
}
if (s > W) return 0;
return 1;
}
void sol(int bt[], int &vmax, int val[]) {
int s = 0;
for (int i = 0; i <= k; i++) {
s += val[bt[i]];
}
if (s > vmax) {
vmax = s;
}
}
int main() {
int N, G;
scanf("%d %d", &N, &G);
for (int i = 0; i < N; ++i) {
scanf("%d %d", &W[i], &P[i]);
}
int bt[N];
int as, ev;
int vmax = -1;
init(bt);
while (k >= 0) {
do {
as = succesor(bt, N);
if (as) {
ev = valid(bt, wt, G);
}
} while (as && !ev);
if (as) {
sol(bt, vmax, val);
k++;
init(bt);
} else {
k--;
}
}
printf("%d", vmax);
return 0;
}