I still don't know what the algorithm is trying to do but the non-recursive function could be:
public static int findMaxRec_NonRecursive(int[] Vect_w, int[] Vect_v, int W, int n)
{
List<int> prevWValues = new List<int>();
List<int> prevVValues = new List<int>();
List<int> prevIndex_i = new List<int>();
List<int> prevMaxValue = new List<int>();
int ListIndex = 0, iniIndex = 0, max = int.MinValue;
startOver:
for (int i = iniIndex; i < n; i++)
{
if (Vect_w[i] <= W)
{
if (Vect_w[i] == W)
max = Math.Max(Vect_v[i], max);
else
{
if (prevWValues.Count > ListIndex)
{
prevWValues[ListIndex] = W;
prevIndex_i[ListIndex] = i;
prevVValues[ListIndex] = Vect_v[i];
prevMaxValue[ListIndex] = max;
}
else
{
prevWValues.Add(W);
prevIndex_i.Add(i);
prevVValues.Add(Vect_v[i]);
prevMaxValue.Add(max);
}
W -= Vect_w[i];
ListIndex++;
iniIndex = 0;
max = int.MinValue;
goto startOver;
}
}
}
if (ListIndex>0)
{
ListIndex--;
iniIndex = prevIndex_i[ListIndex]+1;
W = prevWValues[ListIndex];
max = Math.Max(max+ prevVValues[ListIndex], prevMaxValue[ListIndex]);
goto startOver;
}
return max;
}
Sorry for the 'gotos', I just found it easier to program for this case. Also I have renamed a little your input variables not to drive crazy.
EDIT
As others have pointed out, it could be used as a Knapsack algorithm, so knowing what it is intended to do, you could optimize/simplify a little more (the complexity of these kind of algorithms grow exponentially with n). For instance, you can sort the input Vect_W values and replace lists by arrays.
public static int findMaxRec_NonRecursive(int[] Vect_w, int[] Vect_v, int W, int n)
{
Array.Sort(Vect_w, Vect_v);
n = Math.Min(n, Vect_w.Length);
//Remove here repeated elements in Vect_w selecting the one with higher Vect_v if uniqueness is not assured
int minVectW = Vect_w[0];
int L = W / minVectW + 1;
int[] prevWValues = new int[L];
int[] prevVValues = new int[L];
int[] prevIndex_i = new int[L];
int[] prevMaxValue = new int[L];
int ListIndex = 0, iniIndex = n - 1, max = int.MinValue, PrevUsefullIndex = 0;
startOver:
for (int i = iniIndex; i >= 0; i--)
{
if (Vect_w[i] <= W)
{
if (PrevUsefullIndex < i)
PrevUsefullIndex = i;
if (Vect_w[i] == W)
max = Math.Max(Vect_v[i], max);
else
{
int newW = W - Vect_w[i];
if (newW < minVectW)
max = Math.Max(Vect_v[i], max);
else
{
prevWValues[ListIndex] = W;
prevIndex_i[ListIndex] = i;
prevVValues[ListIndex] = Vect_v[i];
prevMaxValue[ListIndex] = max;
W = newW;
ListIndex++;
iniIndex = PrevUsefullIndex;
PrevUsefullIndex = 0;
max = int.MinValue;
goto startOver;
}
}
}
}
if (ListIndex > 0)
{
ListIndex--;
iniIndex = prevIndex_i[ListIndex] - 1;
W = prevWValues[ListIndex];
max = Math.Max(max + prevVValues[ListIndex], prevMaxValue[ListIndex]);
goto startOver;
}
return max;
}
EDIT 2
I just found out that the initial recursive algorithm posted is not well conditioned, for example in the case where the best branch is the first branch. I think it should have an additional condition to avoid that:
//[...]
else
{
int innerMax = findMaxRec(w, v, W - w[i], n);
if (innerMax == int.MinValue)
innerMax = 0;
res = innerMax + v[i];
}
//[...]
I have also added a condition in the non-recursive algorithm that does pretty much the same by checking if the branch can be officialy closed when the new W is lower than the smallest vect_W element.
// Input: // Values (stored in array v) // Weights (stored in array w) // Number of distinct items (n) // Knapsack capacity (W)Without any comment on naming the variable name must speak for themself.