Solved

# MFKnapsack(i, j)  = Can someone help me understand this psuedocode and convert it to C++

Posted on 2006-06-06
670 Views
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]
0
Question by:warriorfan808

LVL 4

Accepted Solution

Knapsack problem is a typical dynamic programming example see http://en.wikipedia.org/wiki/Dynamic_programming

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
0

LVL 1

Author Comment

Thanks guys.  I understand how it works, just not good at implimenting.  Later today, I'll try and translate it to C++ and hopefully someone on here can help me figure out what I'm doing wrong.  Learning off of psuedocode is still uncomfortable for me.  I'm use to going through the book, looking at code, seeing how it works and then implimenting some of the things I see in my own code.  Just picking up techniques from other programs.
0

## Featured Post

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.