#include <iostream>
#include <cstring>
#include <ctime>

typedef struct{
	int size;
	int val;
} Item;

const int n = 10;	// Число предметов
const int m = 50;	// Емкость рюкзака
const int size = 50;

Item items[n];
int max_known[size];
Item item_known[size];

int knap(int cap){
	int space;
	int max;
	int maxi;
	int t;

	for(int i = 0; i < size; i++)
		std::cout << max_known[i] << " ";
	std::cout << std::endl;

	if(max_known[cap] != -1) return max_known[cap];
	for(int i = 0, max = 0; i < n; i++)
		if((space = cap - items[i].size) >= 0)
			if((t = knap(space) + items[i].val) > max){
				max = t;
				maxi = i;
			}
	max_known[cap] = max;
	item_known[cap] = items[maxi];
	return max;
}


int main(){
	std::memset(max_known, -1, size * sizeof(int));

	// Создаем рандомные вещи
	std::srand(time(NULL));
	for(int i = 0; i < n; i++){
		Item it;
		it.size = 1 + std::rand() % 15;
		it.val = 1 + std::rand() % 701;
		items[i] = it;
	}

	std::cout << knap(m) << std::endl;

	int pause;
	std::cin >> pause;
}