Я написал функцию с именем rucksack
, которая принимает линейный список и ограничитель, который ограничивает вес. Функция возвращает максимальную стоимость выбранных предметов, которые вы можете выбрать, не превышая вес 4500.
#include <stdio.h>
struct item {
int weight; // Artikelgewicht in Gramm
int value; // Artikelwert in Euro
int stock; // Vorhandene Artikelmenge
struct item *next;
};
struct item laptop = {1500, 1000, 3, NULL};
struct item tablet = { 700, 300, 2, &laptop};
struct item mobile = { 180, 500, 2, &tablet};
struct item *items = &mobile;
int max(int a,int b)
{
return a > b ? a : b ;
}
int rucksack ( struct item* item , int limit)
{
if (item == NULL)
return 0 ;
int sum = 0 ;
for (int i = 0 ; i<= item->stock && i * item->weight<=limit ; i++)
sum = max(sum, i * item->value + rucksack (item->next , limit - i*item->weight )) ;
return sum;
}
int main() {
printf("%d", rucksack(items, 4500));
}
Я хочу знать, какая комбинация предметов была выбрана, но я не знаю, как реализовать это в моем рекурсии. Кто-нибудь может помочь?