Pasted

#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;
}