ПРОШУ С++ ПОМОГИТЕ

Это классическая задача о рюкзаке (Knapsack problem). Вот решение на C++ с использованием динамического программирования:

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void knapsack(int capacity, vector<int> weights, vector<int> values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

// Заполняем таблицу dp
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i-1] <= w)
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}

// Восстанавливаем решение
vector<int> selected_items;
int w = capacity;
int i = n;

while (i > 0 && w > 0) {
if (dp[i][w] != dp[i-1][w]) {
selected_items.push_back(i-1);
w -= weights[i-1];
}
i--;
}

// Вывод результатов
cout << "Максимальная стоимость: " << dp[n][capacity] << endl;
cout << "Выбранные предметы (индексы): ";
for (int i = selected_items.size()-1; i >= 0; i--)
cout << selected_items[i] << " ";
cout << endl;
}

int main() {
int n, capacity;

cout << "Введите количество предметов: ";
cin >> n;
cout << "Введите вместимость рюкзака: ";
cin >> capacity;

vector<int> weights(n);
vector<int> values(n);

cout << "Введите вес и стоимость каждого предмета:\n";
for (int i = 0; i < n; i++) {
cout << "Предмет " << i << " (вес стоимость): ";
cin >> weights[i] >> values[i];
}

knapsack(capacity, weights, values);

return 0;
}
```

Алгоритм работает следующим образом:
1. Создаем таблицу dp, где dp[i][w] хранит максимальную стоимость для первых i предметов и вместимости w
2. Заполняем таблицу, используя принцип динамического программирования
3. После заполнения восстанавливаем решение, определяя какие предметы были выбраны
4. Выводим максимальную возможную стоимость и список выбранных предметов

Программа запрашивает:
- Количество предметов
- Вместимость рюкзака
- Вес и стоимость каждого предмета

Затем выводит оптимальное решение - максимальную стоимость и список выбранных предметов.