#include <iostream>
#include <vector>

using namespace std;

int n; // Кол-во предметов

int max_weight; // Максимальный вес предметов

vector<int> item_weight; // Вес предметов
vector<int> item_cost; // Цена предметов

inline int getCost(vector<bool> &mask) {
	int result = 0;
	for (int i = 0; i < n; ++i) {
		if (mask[i]) result += item_cost[i];
	}
	return result;
}

void knapsack() {
	const unsigned int nIterations = 1 << n; // количество комбинаций, 2^n
	int sum = 0;      // текущий вес вещей
	int cost = 0;     // текущая стоимость вещей

	int bestCost = 0; // максимальная стоимость стоимость (максимальная, без перегрузки)
	int bestSum = 0;  // вес при максимальной стоимости

	vector<bool> mask(n);               // текущая комбинация выбранных вещей
	vector<bool> bestMask(n);           // лучшая комбинация выбранных вещей

	for (unsigned int i = 1; i < nIterations; i++) {

		// какой по счёту бит инвертируем
		unsigned long position;    
		_BitScanForward(&position, i);
		mask[position] = !mask[position];
		
		// кладём в рюкзак или убираем эту вещь
		if (mask[position]) sum += item_weight[position];
		else sum -= item_weight[position];

		// перегруз
		if (sum > max_weight) continue;

		cost = getCost(mask);
		// Если цена текущего набора больше цены максимального
		if (cost > bestCost) {
			// Отличный вариант! Надо запомнить...
			bestCost = cost;
			bestMask = mask;
			bestSum = sum;
		}
	}

	cout << "Вес у максимальной цены: " << bestSum << endl;
	cout << "Максимальная цена: " << bestCost << endl;
	cout << "Используемые веса:";
	for (int i = 0; i < 5; i++)
		if (bestMask[i]) cout << " " << item_weight[i];
	cout << endl;
}

int main() {
	setlocale(LC_ALL, "Russian");
	
	// Сюда засунуть ввод
	item_weight = { 1, 9, 2, 3, 5};
	item_cost = { 50, 700, 300, 200, 500 };
	max_weight = 10;
	n = 5;

	knapsack();
	system("pause");
	return 0;
}