3 
    public static int n;
    public static int w;
    public static int[] s;
    public static int[] p;

    static void Main(string[] args)
    {
        n = 5;
        w = 5;

        s = new int[n + 1];
        p = new int[n + 1];
        Random rnd = new Random();

        for (int i = 1; i <= n; i++)
        {

            s[i] = rnd.Next(1, 10);
            p[i] = rnd.Next(1, 10);
        }

        Console.WriteLine(F_recursion(n, w));
        Console.WriteLine(DP(n, w));
    }

    // recursive approach
    public static int F_recursion(int n, int w)
    {
        if (n == 0 || w == 0)
            return 0;
        else if (s[n] > w)
            return F_recursion(n - 1, w);
        else
        {                          
            return Math.Max(F_recursion(n - 1, w), (p[n] + F_recursion(n - 1, w - s[n])));
        }
    }

    // iterative approach
    public static int DP(int n, int w)
    {
        int result = 0;

        for (int i = 1; i <= n; i++)
        {

            if (s[i] > w)
            {
                continue;
            }
            else
            {                   
                result += p[i];
                w = w - s[i];
            }
        }

        return result;
    }

I need to convert F_recursion function to iterative. I currently written following function DP that sometimes works but not always. I learned that problem is in F_recursion(n - 1, w - s[n]) I have no idea how to make w - s[n] work correctly in iterative solution. If change w - s[n] and w - s[i] to only w then program always work.

In Console:

s[i] = 2 p[i] = 3
-------
s[i] = 3 p[i] = 4
-------
s[i] = 5 p[i] = 3
-------
s[i] = 3 p[i] = 8
-------
s[i] = 6 p[i] = 6
-------
Recursive:11
Iteration:7

but sometimes it works

s[i] = 5 p[i] = 6
-------
s[i] = 8 p[i] = 1
-------
s[i] = 3 p[i] = 5
-------
s[i] = 3 p[i] = 1
-------
s[i] = 7 p[i] = 7
-------
Recursive:6
Iteration:6
Improve this question
5
  • 6
    Define "sometimes works but not always". Commented May 11, 2017 at 8:45
  • Added example what result I get after I run program several times. Commented May 11, 2017 at 8:57
  • Okay, great... now what do these numbers mean? What does your recursive method actually do? Commented May 11, 2017 at 8:59
  • Method is recurrence relation, which I converted to recursive version which works fine but I don't know how to convert it to iterative version. s, p are just an arrays where I store random numbers. Commented May 11, 2017 at 9:19
  • 2
    That's what it is, not what it does. At any rate, your iterative method doesn't look much like your recursive method. You have no checks for the value of w, no call to Math.Max, and I can't see how it would be replicating the possible branching recursion. From what I can tell, you've implemented just enough of the iterative method for it to replicate the recursive method on a very particular kind of input only. Commented May 11, 2017 at 9:31

2 Answers 2

Reset to default
2

The following approach might be useful, when bigger numbers are involved (specially for s) and consequently a 2 dimensional array would be unnecessary big and only a few w values would actually be used in computing the result.

The idea: precompute possible w values, by starting at w and for each i in [n, n-1, ..., 1] determine the values w_[i], where w_[i+1] >= s[i] without duplicates. Then iterate i_n over n and compute sub-results only for valid w_[i] values.

I chose an array of Dictionary as datastructure, since it's relatively easy to design sparse data this way.

public static int DP(int n, int w)
{
    // compute possible w values for each iteration from 0 to n
    Stack<HashSet<int>> validW = new Stack<HashSet<int>>();
    validW.Push(new HashSet<int>() { w });
    for (int i = n; i > 0; i--)
    {
        HashSet<int> validW_i = new HashSet<int>();
        foreach (var prevValid in validW.Peek())
        {
            validW_i.Add(prevValid);
            if (prevValid >= s[i])
            {
                validW_i.Add(prevValid - s[i]);
            }
        }
        validW.Push(validW_i);
    }

    // compute sub-results for all possible n,w values.
    Dictionary<int, int>[] value = new Dictionary<int,int>[n + 1];
    for (int n_i = 0; n_i <= n; n_i++)
    {
        value[n_i] = new Dictionary<int, int>();
        HashSet<int> validSubtractW_i = validW.Pop();
        foreach (var w_j in validSubtractW_i)
        {
            if (n_i == 0 || w_j == 0)
                value[n_i][w_j] = 0;
            else if (s[n_i] > w_j)
                value[n_i][w_j] = value[n_i - 1][w_j];
            else
                value[n_i][w_j] = Math.Max(value[n_i - 1][w_j], (p[n_i] + value[n_i - 1][w_j - s[n_i]]));
        }
    }

    return value[n][w];
}

It's important to understand that some space and computation is "wasted" in order to precompute possible w values and to support the sparse data structures. So this approach might perform bad for large data sets with small values in s, where most w values will be possible sub-results.

After some more thought I realized, if space is a concern, you can actually throw away the sub-results of everything except the previous outer loop iteration, since the recursion in this algorithm follows a strict n-1 pattern. However, I'm not including this into my code for now.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Your approach does not work because your dynamic programmig state space (which apparently is only one variable) does not match the signature of the recursive method. The goal of the dynamic programming approach should be to define and fill a state space such that all results for evaluation are available when needed. On inspection of the recursive method, notice that the recursive calls of F_recursion may change both arguments, n and w. This is an indication that a two-dimensional state space should be used.

The first argument (which apparently limits the range of items) can range from 0 to n while the second argument (which apparently is some bound for the total of an item property) can range from 0 to w.

You should define a two dimensional state space

int[,] value = new int[n,w];

for accomodation of the values. Next, you should initialize the values to undefined; you can use the value Int32.MaxValue for this, because it will behave in a suitable way if the minimum with some different value is calculated.

Next, the iterative version of the algorithm shoud use two loops which iterate in a forwad manner, unlike the recursive iteration which decreases the arguments.

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < w; j++)
    {
        // logic for the recurrence relation goes here
    }
}

In the innermost block you can use a modified version of the recurrence relation. Instead of using recursive calls, you access values which are stored in value; instead of returning values, you write the values to value.

Semantically this is the same as memoization, but instead of using actual recursive calls, the order of evaluation asserts that necessary values always exist, making additional logic unneccessary.

Once the state space is filled, you have to examine its last state (namely the part of the array where the first index is n-1) to determine the maximal value for the entire input.

Improve this answer

4 Comments

With random values <= 10 and n, w starting at 5 this may be suitable, but for larger values a lot of computation will be wasted by not considering the gaps in w values...
@grek40 You mean that more states than necessary are evaluated?
Yes... and I feel like there is a way to limit the computed w values by restricting valid subsets with sum(s[i]) <= w. But haven't completed this train of thought.
@grek40 You are absolutely right; but simply adding memoization to the recursive implementation does not remove the recursion (the removal of which the question explicitly demands).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.