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

Posted on 2006-06-06
Last Modified: 2006-11-18
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)

        value <-- max(MFKnapsack(i -1, j),
            Values[i] + MFKnapsack(i -1, j - Weights[i]))
    V[i, j} <-- value

return V[i, j]
Question by:warriorfan808
    LVL 4

    Accepted Solution

    Knapsack problem is a typical dynamic programming example see

    It is explained in more detail at

    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
    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.

    Featured Post

    What Is Threat Intelligence?

    Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

    Join & Write a Comment

    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 (…
    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.

    728 members asked questions and received personalized solutions in the past 7 days.

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

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    20 Experts available now in Live!

    Get 1:1 Help Now