Top.Mail.Ru
Ответы

С++ ПОМОГИТЕ ПЖ

Дано n предметов массой m1.....mn и стоимостью c1....cn соответственно. Ими наполняют рюкзак, который выдерживает вес не более . Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

Входные данные

4 6
2 4 1 2
7 2 5 1
Результат работы

3
4 3 1

По дате
По рейтингу
Аватар пользователя
Новичок
7мес

Это классическая NP-полная https://ru.wikipedia.org/wiki/Задача_о_рюкзаке , стандартно решаемая полным перебором. В указанной статье Wiki приведены алгоритмы более эффективных способов решений.

Аватар пользователя
Просветленный
7мес
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
 #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; 
} 
 
Аватар пользователя
Ученик
7мес

# Данные
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).

Аватар пользователя
Профи
7мес

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