Мне нужно написать код с помощью графов. Код должен простой (начального уровня) . Вот условия задачи:Дано список предметов, каждый предмет обладает своей массой и ценой. Дан рюкзак, который ограничен максимальным переносимым весом. Найти такой набор предметов, влезающих в рюкзак, ценность которых максимальна.
#include <iostream #include <vector> const int MAX_WEIGHT = 100; // Максимально допустимая масса рюкзака struct Item { int weight; // Масса предмета int value; // Ценность предмета }; std::vector<Item> items; // Список предметов // Рекурсивная функция для поиска набора предметов с максимальной ценностью int findBestSet(int weight, int itemIndex) { if (weight <= 0 || itemIndex < 0) { return 0; // Базовый случай: рюкзак уже заполнен или все предметы уже проверены } int valueWithoutItem = findBestSet(weight, itemIndex - 1); // Рекурсивный вызов без текущего предмета if (items[itemIndex].weight > weight) { return valueWithoutItem; // Текущий предмет слишком тяжелый } int valueWithItem = findBestSet(weight - items[itemIndex].weight, itemIndex - 1) + items[itemIndex].value; // Рекурсивный вызов с текущим предметом return std::max(valueWithoutItem, valueWithItem); // Вернуть максимум из двух вариантов } int main() { // Заполните список items тестовыми данными std::cout << "Max value: " << findBestSet(MAX_WEIGHT, items.size() - 1) << std::endl; return 0; } C #include <iostream #include <vector> const int MAX_WEIGHT = 100; // Максимально допустимая масса рюкзака struct Item { int weight; // Масса предмета int value; // Ценность предмета }; std::vector<Item> items; // Список предметов // Рекурсивная функция для поиска набора предметов с максимальной ценностью int findBestSet(int weight, int itemIndex) { if (weight <= 0 || itemIndex < 0) { return 0; // Базовый случай: рюкзак уже заполнен или все предметы уже проверены } int valueWithoutItem = findBestSet(weight, itemIndex - 1); // Рекурсивный вызов без текущего предмета if (items[itemIndex].weight > weight) { return valueWithoutItem; // Текущий предмет слишком тяжелый } int valueWithItem = findBestSet(weight - items[itemIndex].weight, itemIndex - 1) + items[itemIndex].value; // Рекурсивный вызов с текущим предметом return std::max(valueWithoutItem, valueWithItem); // Вернуть максимум из двух вариантов } int main() { // Заполните список items тестовыми данными std::cout << "Max value: " << findBestSet(MAX_WEIGHT, items.size() - 1) << std::endl; return 0; }
Katsuzor, чел попросил простой код скорее всего для универа. Если да, то будет прикол если они вектора и структуры не изучали
#include <iostream> #include <vector> using namespace std; const int N = 1010, M = 10010; int n, m; int w[N], c[N]; int dp[M]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> w[i] >> c[i]; for (int i = 1; i <= n; i++) for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + c[i]); cout << dp[m] << endl; return 0; } C #include <iostream> #include <vector> using namespace std; const int N = 1010, M = 10010; int n, m; int w[N], c[N]; int dp[M]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> w[i] >> c[i]; for (int i = 1; i <= n; i++) for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + c[i]); cout << dp[m] << endl; return 0; }