Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Solved

Posted on 2006-06-06

I'm having a real hard time understanding this. I had a friend that told me I will be tested on this algorithm, so I'm trying to figure it out. I want to convert it to C++ and mess with it.

/Implements the memoryfunction method for the knapsack problem

I//nput: A nonnegative integer i indicating the number of the first

// items being considered and a nonnegative integer j indicating the knapsack's capacity

//Output: The value of an optimal feasible subset of the first i items

//Note: Uses as global variables input arrays Weights[1..n], Values[1...n]

//and table V[0...n, 0...W] whose entries are initialized with -1's except for

//row 0 and column 0 initialized with 0's

if V[i, j] < 0

if j < Weights[i]

value <-- MFKnapsack(i - 1, j)

else

value <-- max(MFKnapsack(i -1, j),

Values[i] + MFKnapsack(i -1, j - Weights[i]))

V[i, j} <-- value

return V[i, j]

/Implements the memoryfunction method for the knapsack problem

I//nput: A nonnegative integer i indicating the number of the first

// items being considered and a nonnegative integer j indicating the knapsack's capacity

//Output: The value of an optimal feasible subset of the first i items

//Note: Uses as global variables input arrays Weights[1..n], Values[1...n]

//and table V[0...n, 0...W] whose entries are initialized with -1's except for

//row 0 and column 0 initialized with 0's

if V[i, j] < 0

if j < Weights[i]

value <-- MFKnapsack(i - 1, j)

else

value <-- max(MFKnapsack(i -1, j),

Values[i] + MFKnapsack(i -1, j - Weights[i]))

V[i, j} <-- value

return V[i, j]

2 Comments

It is explained in more detail at http://en.wikipedia.org/wiki/Knapsack_problem

So we have a big list of items of various sizes to fit in a knapsack of a fixed size. The idea is that we calculate the values for all knapsack sizes, so that when we have any spaces left, we use our knowledge of previous solutions to fill things in.

For example, let's say the knapsack size is 10. We'll start the most items we can fit in at sizes, 1, 2, 3 ..., 10. By the time we get to size 7 (for example), we already know the optimal items to put in to fill in a size 3 problem and we can just do that. (A very rough description, but enough to get the general idea).

As Venabili says, doing homework is against the rules, so perhaps if you post some example code or have a stab at it, we can help you out some more.

I'm guessing the MF (memory function) is just memoisation (or at least I assume it is, maybe you have some other complicated technique for the knapsack problem). Memoisation is just recalling previous results, without repeating calculations, see http://en.wikipedia.org/wiki/Memoization

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Course of the Month14 days, 18 hours left to enroll

Join the community of 500,000 technology professionals and ask your questions.