Knapsack Problem
Lesson 7 of 15 in Coddy's Recursion Challenges - Master The Recursive Thinking course.
Challenge
MediumThe knapsack problem is a famous problem.
In this problem, you have a knapsack that has a predefined weight it can take and items where each item has a weight and a value.
Your task is to take as much value in the bounds of the knapsack weight.
For example,
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Weight of knapsack - 10
The solution is to take the items with the weights 1 and 8 and the values 20 and 40.
The max value is 60, and the total weight is 9 (which is smaller or equals 10 meaning that it is a valid weight).
Write a function named knapsack that gets an integer W and two arrays of integers values and weights and returns the solution for the knapsack problem using the input values (the maximum value the knapsack can take).
Try it yourself
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Write code here
return 0;
}
All lessons in Recursion Challenges - Master The Recursive Thinking
2Medium Challenges
Knapsack ProblemNumber of SquaresInterleaving ResultSum CombinationsFind TripletSplit Array