# Cod sursa(job #827067)

Utilizator Data 1 decembrie 2012 16:26:56 Ghiozdan 30 cpp done Arhiva de probleme 1.17 kb
``````#include <fstream>
#include <string.h>
#include <vector>

#define MAX_N ((const unsigned int)20000)
#define MAX_G ((const unsigned int)75000)
#define INFINITE ((const unsigned int)-1000000)

typedef std::vector<int>		Vector;

int N, G;

int w[MAX_N];
unsigned int min[MAX_G];

Vector sol[MAX_G];
Vector solFin;

unsigned int nr = INFINITE;
unsigned int weight = 0;

int main()
{
std::ifstream fin("ghiozdan.in");
std::ofstream fout("ghiozdan.out");

fin>>N>>G;

for (int i = 0; i < N; ++ i)
fin>>w[i];

memset(min, INFINITE, sizeof(int) * MAX_G);

min[0] = 0;

for (int i = 0; i < N; ++ i)
{
for (int j = G - w[i]; j >= 0; -- j)
{
if (min[j + w[i]] > min[j] + 1)
{
min[j + w[i]] = min[j] + 1;
sol[j + w[i]] = sol[j];
sol[j + w[i]].push_back(i);

if (j + w[i] >= weight)
{
if (weight != j + w[i])
weight = j + w[i];

if (nr != min[j + w[i]])
{
nr = min[j + w[i]];
solFin = sol[j + w[i]];
}
}
}
}
}

fout<<weight<<" "<<nr<<'\n';

for (int i = 0; i < solFin.size(); ++ i)
fout<<solFin[i]<<'\n';

fin.close();
fout.close();

return 0;
}``````