Knapsack Problem
Урок 7 из 15 курса Задачи на рекурсию: освойте рекурсивное мышление на Coddy.
Задание
СреднеЗадача о рюкзаке — это знаменитая задача.
В этой задаче у вас есть рюкзак, который имеет заранее определенный вес, который он может выдержать, и предметы, где каждый предмет имеет вес и ценность.
Ваша задача — набрать как можно больше ценности в пределах веса рюкзака.
Например,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Вес рюкзака - 10
Решение состоит в том, чтобы взять предметы с весами 1 и 8 и ценностями 20 и 40.
Максимальная ценность составляет 60, а общий вес равен 9 (что меньше или равно 10, что означает, что это допустимый вес).
Напишите функцию с именем knapsack, которая принимает целое число W и два массива целых чисел values и weights и возвращает решение задачи о рюкзаке, используя входные значения (максимальную ценность, которую может вместить рюкзак).
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Напишите код здесь
return 0;
}
Все уроки раздела Задачи на рекурсию: освойте рекурсивное мышление
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array