Hi guys,
i'm reading a few examples about recurtion in the internet and came across this example: The 0-1 Knapsack Problem In C | DZone
two things:
1. is this a recursive code ?
2. how can i write it in a more general way.. say i have N items and N<=30, and the value is V and weight is Wi and maximum wegight is W?
in this case i still need the difine ?
thanks.
There are certainly better examples of the knapsack problem, with better variable names, better indentation, better code organization, better scalability, etc. Also, if you examine the algorithm, or read the comments, you will find out that it does not provide a solution to the 0-1 knapsack problem. It is unbounded, letting you reuse items.
1. Does the fill_sack function ever call itself? No. Thus that is not recursive code. It is common to see a recursive solution to the knapsack problem though.
2. Google for other examples and see what they do. You need to change n, c and v in the example you provided, to reflect the right number of items, the right costs and right values. You can do that by adding a loop to ask the user for input of how many items, and what each one is.
Here, for instance, is a better example of the 0-1 knapsack: Knapsack problem/0-1 - Rosetta Code. Can you figure out if that one is recursive?
I guess you are learning recursion about know.Knapsack problem is a very good example for algorithms and complexity,so i would suggest you to try learning recursion and after gaining experience return to the problem and face it (both the discrete and the non-discrete versions because greedy strategy gives the optimum solution to the non-discrete one,but not in the other etc..shall not tell more now in order not to complex you)
1-Is this a recursive code?
Oh anduril already answered
