knack

/*
Задача о рюкзаке на c++
Кол-во предметов: 1900, диапазон весов: 29 — макс вес., 1 — мин вес. Веса распределяются равномерно (вероятность равная для любого веса). Стоимость предметов — от 1 до 2 (double) — равновероятно. (т. е. Все рандомить и переводить даблом). Макс вес — 500. Найти такую комбинацию предметов, наименьшую по весу и наибольшую по стоимости, чтобы помещалась в рюкзак.
И выводить именно набор предметов
Напишите пожалуйста код на c++
*/
#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
using  TVWeight = std::vector <int>;
using  TVCost = std::vector <double>;

/**
 * @brief knack
 * @param K емкость рюкзака
 * @param W вектор с весами предметов
 * @param C вектор со стоимостями
 * @param res указатель на вектор, для возврата индексов предметов
 * @return максимальная полученная стоимость
 */
double knack (int K, const TVWeight & W, const TVCost & C,
              std::vector<int> & res) {
    int N = W.size(); // количество предметов
    std::vector<TVCost> F(N + 1, TVCost (K + 1, 0));
    for (auto i = 1; i < N + 1; ++i)
        for (auto k = 1; k < K + 1; ++k)
            if (k >= W[i - 1])
                F[i][k] = std::max(F[i - 1][k], F[i - 1][k - W[i - 1]] + C[i - 1]);
            else
                F[i][k] = F[i - 1][k];
    for (auto i = N, k = K; i > 0; --i) {
        if (F[i][k] != F[i -1][k]) {
            res.push_back(i - 1);
            k -= W[i - 1];
        }
    }
    return F[N][K];
}
int main() {
    int n = 1900;
    std::vector<int> W (n);
    std::vector<double> C (n);
    std::mt19937 gen{ std::random_device()()};
    std::uniform_int_distribution<> dis(1, 29);
    std::uniform_real_distribution<> dis2(1.0, 2.0);
    auto rand1 = [&] { return dis(gen); };
    auto rand2 = [&] { return dis2(gen); };
    generate(W.begin(), W.end(), rand1);
    generate(C.begin(), C.end(), rand2);

    std::vector<int> res;
    double m = knack(500, W, C, res);
    for (auto i: res)
        std::cout << i << " "; // индекс предмета
    std::cout << "\nresult: " << m;

}