Problem plecakowy
Lekcja 7 z 15 w kursie Wyzwania z rekurencji — opanuj myślenie rekurencyjne w Coddy.
Wyzwanie
ŚredniProblem plecakowy jest znanym problemem.
W tym problemie masz plecak o określonej maksymalnej wadze oraz przedmioty, z których każdy ma swoją wagę i wartość.
Twoim zadaniem jest zmieścić w plecaku przedmioty o jak największej łącznej wartości, nie przekraczając jego maksymalnej wagi.
Na przykład:
values - [20, 5, 40, 10, 15]
weights - [1, 2, 8, 3, 7]
Waga plecaka - 10
Rozwiązaniem jest wybranie przedmiotów o wagach 1 i 8 oraz wartościach 20 i 40.
Maksymalna wartość wynosi 60, a łączna waga to 9 (czyli jest mniejsza od lub równa 10, co oznacza, że spełnia ograniczenie wagowe).
Napisz funkcję o nazwie knapsack, która przyjmuje liczbę całkowitą W oraz dwie tablice liczb całkowitych values i weights, a następnie zwraca rozwiązanie problemu plecakowego dla podanych wartości (maksymalną wartość, jaką można zmieścić w plecaku).
Spróbuj swoich sił
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// Wpisz kod tutaj
return 0;
}
Wszystkie lekcje w sekcji Wyzwania z rekurencji — opanuj myślenie rekurencyjne
2Średnio zaawansowane wyzwania
Problem plecakowyLiczba kwadratówPrzeplatanie wynikówKombinacje sumZnajdź trójkęPodziel tablicęPoćwicz samodzielnie: Kompilator C online