How to Dynamically Program the KnapSack Problem?

Hello All, I got this assignment to do in C++, here's the description.

A restaurant would like to order ~potatoes. They come in many sizes, 1kg, 5kg, 10 kg... Matched up with a price. Now price won't really make sense at times, as long as the algorithm figures out what is the cheapest way to purchase a certain amount KG of potatoes

ex:

This would be in a txt file

3 //Number of potato bag types
20 5 // KG - Price
10 3 // KG - Price
1 1 // KG - Price
28 //Amount in KG to be purchased

Options to obtain 28 KG would be:

20 * 2 = 10 bucks -> waisting potatoes is allowed
10 * 2 + 8 * 1 = 14 bucks
28 * 1 = 28 bucks


Now I would like to know how to structure my code, what will I need to properly sort this data. I do I find all combinations dynamiccally and sort out whats best?

General or specific help would be greatly appreciated.

Thanks lots

How efficient does your program need to be?

I dont understnad the weight and currency but this is bin packing?
sounds like a job for reccursion and trees
ex) to get a weight of 28, you will have 28 levels in your tree, and find paths for every combination adding 1 unit of currency at a time, always choosing the smallest currency first.

level 1: choice from (1, 3, 5)... choose 1
(add weight to global var) (add 1 to a current_path array)
level 2: you have 1 already
choice from (1,3,5)... choose 1 again
(add weight to global var) (add 1 to a current_path array)

...etc...
stop the recurssion when the weight adds up to 28+
at the end if this route has the min cost so far, store the current_path array as the min_path array

in the end you will have one route with all 1s, one route with all 5s, one route with all 3s... and everything in between will be a mixture of currencies

The Program is suppose to be efficient cause I'll be using a timeofday function to time the execution. So it's all about optimizing the calculation part, (((())))) for less multiplication ...


Thanks by the way for the binary tree idea, that's exactly what we are learning in class but not the coding part yet. You know math is almost always on the chalkboard.

Any websites giving tutorials on how to manipulate a binary tree. I get the idea that the root and branches will pick either 1-3-5 and at each pick add the kg_Var corresponding. with a few conditions. But how in the heck do I get started.

1. I got my values in a file, cool
2. ?

; )


I'll keep on researching on this, you put me on the right path and thats what counts right now.

Thank you

Jigger

Does anyone have code(c/c++/java) to how to do the knapsack problem the dynamic way?

The values I must evaluate are lets say

KG / $

2 7
5 11
10 18

I must find the cheapest way to purchase x amount(kg). I'm also allowed to go over the x amount, as long as it's the cheapest solution.

Jigger