Cod sursa(job #1253477)

Utilizator pulseOvidiu Giorgi pulse Data 1 noiembrie 2014 13:25:17
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("date.in");
ofstream fout("date.out");

int N, G;
int value;
struct Rucsac
{
	int g;
	int v;
	int p;
} A[1005];
vector <int> Sol;

bool cmp(Rucsac x, Rucsac y)
{
	if (x.v == y.v) return x.g < y.g;
	return x.v > y.v;
}

int main()
{
	fin >> N >> G;
	for (int i = 1; i <= N; ++i)
	{
		fin >> A[i].g;
		A[i].p = i;
	}
	for (int i = 1; i <= N; ++i) fin >> A[i].v;
	sort(A + 1, A + N + 1, cmp);
	for (int i = 1; i <= N && G >= 0; ++i)
	{
		if (A[i].g <= G)
		{
			G -= A[i].g;
			value += A[i].v;
			Sol.push_back(A[i].p);
		}
	}
	fout << value << '\n';
	for (int i = 0; i < Sol.size(); ++i) fout << Sol[i] << " ";
	return 0;
}