Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

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

Posted on 2006-06-06
Medium Priority
748 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

fffej78 earned 2000 total points
ID: 16840640
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

ID: 16847032
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

Question has a verified solution.

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

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
###### Suggested Courses
Course of the Month14 days, 18 hours left to enroll