Cod sursa(job #827051)
#include <fstream>
#include <string.h>
#define MAX_N ((const unsigned int)20000)
#define MAX_G ((const unsigned int)75000)
#define INFINITE ((const unsigned int)-1000000)
int N, G;
int w[MAX_N];
unsigned int min[MAX_G];
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;
if (j + w[i] >= weight)
{
weight = j + w[i];
nr = min[j + w[i]];
}
}
}
}
fout<<weight<<" "<<nr;
fin.close();
fout.close();
return 0;
}