С++ ПОМОГИТЕ ПЖ
Дано n предметов массой m1.....mn и стоимостью c1....cn соответственно. Ими наполняют рюкзак, который выдерживает вес не более . Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
Входные данные
4 6
2 4 1 2
7 2 5 1
Результат работы
3
4 3 1
Это классическая NP-полная https://ru.wikipedia.org/wiki/Задача_о_рюкзаке , стандартно решаемая полным перебором. В указанной статье Wiki приведены алгоритмы более эффективных способов решений.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> weights(n);
vector<int> values(n);
for (int i = 0; i < n; i++) {
cin >> weights[i];
}
for (int i = 0; i < n; i++) {
cin >> values[i];
}
// Создаем таблицу для динамического программирования
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// Заполняем таблицу
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
// Максимальная стоимость
cout << dp[n][W] << endl;
// Восстанавливаем набор предметов
vector<int> selectedItems;
int w = W;
for (int i = n; i > 0; i--) {
if (dp[i][w] != dp[i - 1][w]) {
selectedItems.push_back(i); // Предмет i был выбран
w -= weights[i - 1]; // Уменьшаем вес
}
}
// Выводим выбранные предметы в обратном порядке
for (int i = selectedItems.size() - 1; i >= 0; i--) {
cout << selectedItems[i] << " ";
}
cout << endl;
return 0;
}
# Данные
weights = [2, 4, 1, 2]
values = [7, 2, 5, 1]
max_weight = 4
# Результат
max_value = knapsack(weights, values, max_weight)
print(max_value)
Выполнение кода
Если мы запустим этот код:
Для предмета 1 с массой 2 и стоимостью 7: максимальная стоимость при весе 2 - 7.
Для предмета 2 с массой 4 и стоимостью 2: максимальная стоимость при весе 4 - 7 (берём предмет 1).
Для предмета 3 с массой 1 и стоимостью 5: можем взять его с предметом 1 (вес 3, стоимость 12) или без него (максимальное получается при весе 4 - 7).
Для предмета 4 с массой 2 и стоимостью 1: вес 2 уже занят, но стоимость не изменится - максимальная всё равно 7.
Результат
Максимальная стоимость, которую можно унести в рюкзаке с весом не более 4, составляет 12 (предметы 1 и 3: масса 2 + 1 = 3, стоимость 7 + 5 = 12).
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, W;
std::cin >> n >> W;
std::vector<int> weights(n);
std::vector<int> values(n);
for (int i = 0; i < n; ++i) {
std::cin >> weights[i];
}
for (int i = 0; i < n; ++i) {
std::cin >> values[i];
}
// Интернетирующий массив для хранения максимальной стоимости
std::vector<int> dp(W + 1, 0);
// Массив для отслеживания выбранных предметов
std::vector<std::vector<bool>> selected(n, std::vector<bool>(W + 1, false));
// Основной процесс наполнения рюкзака
for (int i = 0; i < n; ++i) {
for (int w = W; w >= weights[i]; --w) {
if (dp[w] < dp[w - weights[i]] + values[i]) {
dp[w] = dp[w - weights[i]] + values[i];
selected[i][w] = true;
}
}
}
// Определяем максимальную стоимость
int max_value = dp[W];
// Чтобы вывести набор предметов, которые составляют этот максимальный набор
std::vector<int> items;
for (int i = n - 1, w = W; i >= 0; --i) {
if (selected[i][w]) {
items.push_back(i + 1); // Сохраняем номера предметов (индексация с 1)
w -= weights[i]; // уменьшаем оставшуюся ёмкость
}
}
// Получение количества предметов
std::cout << items.size() << std::endl;
// Вывод номера предметов в порядке убывания
std::reverse(items.begin(), items.end());
for (int item : items) {
std::cout << item << " ";
}
std::cout << std::endl;
return 0;
}