0

I have written a function named rucksack that takes a linear list and a limiter which limits the weight. The function returns the max costs of chosen items you can choose without getting over the weight of 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));
}

I want to know which combination of items was chosen but I do not know how to implement that in my recursion. Do anyone can help?

David C. Rankin
  • 81,885
  • 6
  • 58
  • 85
Logis
  • 1
  • 1
  • Its a linear list. ```Items``` points to mobile while ```mobile->next``` points to ```tablet``` and ```tablet->next``` to ```laptop```. – Logis Feb 08 '20 at 22:58
  • Sorry, yes that makes more sense now. What is your code not doing right? Is it not stopping when the limit is reached, etc..? – David C. Rankin Feb 08 '20 at 23:00
  • It is stopping perfectly and returns 3300 but I want to print which combination of items. Which items were chosen such that their values sumed up results in 3300 – Logis Feb 08 '20 at 23:02
  • 1
    Then you will need to include a `char *name` member of `struct item` that provides the name of the currently processed item in `rucksack` and it looks like you will need to output the `name` and `sum` after your loop but before you return. (or output the `name` when you enter the function and `sum` at the end). – David C. Rankin Feb 08 '20 at 23:06
  • Thank you for the solution approach. I will try to implement that! – Logis Feb 08 '20 at 23:10
  • 1
    You will want to see [How do I solve the 'classic' knapsack algorithm recursively?](https://stackoverflow.com/questions/7774769/how-do-i-solve-the-classic-knapsack-algorithm-recursively) (even though it is java it has relevant information) – David C. Rankin Feb 08 '20 at 23:30

0 Answers0