SHOW:
|
|
- or go back to the newest paste.
| 1 | /* | |
| 2 | Задача о рюкзаке на c++ | |
| 3 | Кол-во предметов: 1900, диапазон весов: 29 — макс вес., 1 — мин вес. Веса распределяются равномерно (вероятность равная для любого веса). Стоимость предметов — от 1 до 2 (double) — равновероятно. (т. е. Все рандомить и переводить даблом). Макс вес — 500. Найти такую комбинацию предметов, наименьшую по весу и наибольшую по стоимости, чтобы помещалась в рюкзак. | |
| 4 | И выводить именно набор предметов | |
| 5 | Напишите пожалуйста код на c++ | |
| 6 | */ | |
| 7 | #include <vector> | |
| 8 | #include <algorithm> | |
| 9 | #include <iostream> | |
| 10 | #include <random> | |
| 11 | using TVWeight = std::vector <int>; | |
| 12 | using TVCost = std::vector <double>; | |
| 13 | ||
| 14 | /** | |
| 15 | * @brief knack | |
| 16 | * @param K емкость рюкзака | |
| 17 | * @param W вектор с весами предметов | |
| 18 | * @param C вектор со стоимостями | |
| 19 | * @param res указатель на вектор, для возврата индексов предметов | |
| 20 | * @return максимальная полученная стоимость | |
| 21 | */ | |
| 22 | double knack (int K, const TVWeight & W, const TVCost & C, | |
| 23 | std::vector<int> & res) {
| |
| 24 | int N = W.size(); // количество предметов | |
| 25 | std::vector<TVCost> F(N + 1, TVCost (K + 1, 0)); | |
| 26 | for (auto i = 1; i < N + 1; ++i) | |
| 27 | for (auto k = 1; k < K + 1; ++k) | |
| 28 | if (k >= W[i - 1]) | |
| 29 | F[i][k] = std::max(F[i - 1][k], F[i - 1][k - W[i - 1]] + C[i - 1]); | |
| 30 | else | |
| 31 | F[i][k] = F[i - 1][k]; | |
| 32 | for (auto i = N, k = K; i > 0; --i) {
| |
| 33 | if (F[i][k] != F[i -1][k]) {
| |
| 34 | res.push_back(i - 1); | |
| 35 | k -= W[i - 1]; | |
| 36 | } | |
| 37 | } | |
| 38 | return F[N][K]; | |
| 39 | } | |
| 40 | int main() {
| |
| 41 | int n = 1900; | |
| 42 | std::vector<int> W (n); | |
| 43 | std::vector<double> C (n); | |
| 44 | std::mt19937 gen{ std::random_device()()};
| |
| 45 | std::uniform_int_distribution<> dis(1, 29); | |
| 46 | std::uniform_real_distribution<> dis2(1.0, 2.0); | |
| 47 | auto rand1 = [&] { return dis(gen); };
| |
| 48 | auto rand2 = [&] { return dis2(gen); };
| |
| 49 | generate(W.begin(), W.end(), rand1); | |
| 50 | generate(C.begin(), C.end(), rand2); | |
| 51 | ||
| 52 | std::vector<int> res; | |
| 53 | double m = knack(500, W, C, res); | |
| 54 | for (auto i: res) | |
| 55 | std::cout << i << " "; // индекс предмета | |
| 56 | std::cout << "\nresult: " << m; | |
| 57 | ||
| 58 | } |
