Knapsack Problem
Lição 7 de 15 do curso Desafios de Recursão - Domine o Pensamento Recursivo da Coddy.
Desafio
MédioO problema da mochila (knapsack problem) é um problema famoso.
Neste problema, você tem uma mochila que possui um peso máximo predefinido que ela pode suportar e itens onde cada item possui um peso e um valor.
Sua tarefa é obter o máximo de valor possível dentro dos limites de peso da mochila.
Por exemplo,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Peso da mochila - 10
A solução é pegar os itens com os pesos 1 e 8 e os valores 20 e 40.
O valor máximo é 60, e o peso total é 9 (que é menor ou igual a 10, significando que é um peso válido).
Escreva uma função chamada knapsack que recebe um número inteiro W e dois arrays de inteiros values e weights e retorna a solução para o problema da mochila usando os valores de entrada (o valor máximo que a mochila pode suportar).
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Escreva o código aqui
return 0;
}
Todas as lições de Desafios de Recursão - Domine o Pensamento Recursivo
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array