warriorfan808
asked on
MFKnapsack(i, j) = Can someone help me understand this psuedocode and convert it to C++
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]
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER