使用动态规划递归到迭代转换

Question

    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;
    }

我需要将 F_recursion 函数转换为迭代函数。我目前编写了以下函数 DP，它有时有效但并非总是有效。我了解到问题出在 F_recursion(n - 1, w - s[n]) 我不知道如何使 w - s[n] 在迭代中正确工作解决方案。如果将 w - s[n] 和 w - s[i] 更改为仅 w，则程序始终有效。

在控制台中：

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

但有时它有效

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

Answer 1

您的方法不起作用，因为您的动态编程状态 space（显然只是一个变量）与递归方法的签名不匹配。动态规划方法的目标应该是定义和填充状态 space，以便在需要时可以使用所有评估结果。在检查递归方法时，请注意 F_recursion 的递归调用可能会更改两个参数，n 和 w。这表明应使用二维状态 space。

第一个参数（显然限制了项目的范围）可以从 0 到 n 而第二个参数（这显然是一个项目的总和属性) 的范围可以从 0 到 w.

你应该定义一个二维状态space

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

用于调整值。接下来，您应该将值初始化为未定义；您可以为此使用值 Int32.MaxValue，因为如果计算具有某些不同值的最小值，它将以合适的方式运行。

接下来，该算法的迭代版本应该使用两个以正向方式迭代的循环，这与减少参数的递归迭代不同。

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

在最里面的块中，您可以使用递归关系的修改版本。您不使用递归调用，而是访问存储在 value 中的值；不是返回值，而是将值写入 value.

在语义上这与 memoization 相同，但不是使用实际的递归调用，评估顺序断言必要的值始终存在，从而不需要额外的逻辑。

一旦状态 space 被填充，您必须检查其最后状态（即第一个索引为 n-1 的数组部分）以确定整个输入的最大值.

Answer 2

以下方法可能有用，当涉及更大的数字时（特别是 s），因此二维数组不必要大，实际上只会使用几个 w 值在计算结果中。

想法：通过从 w 开始并为每个 i in [n, n-1, ..., 1] 确定值 w_[i]，预先计算可能的 w 值，其中 w_[i+1] >= s[i] 没有重复. 然后在 n 上迭代 i_n 并仅为有效的 w_[i] 值计算子结果。

我选择了一个 Dictionary 的数组作为数据结构，因为这样设计稀疏数据相对容易。

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];
}

重要的是要了解一些 space 和计算 "wasted" 以便预先计算可能的 w 值并支持稀疏数据结构。因此，对于 s 中具有小值的大型数据集，这种方法可能表现不佳，其中大多数 w 值可能是子结果。

经过深思熟虑，我意识到，如果 space 是一个问题，你实际上可以丢弃除先前外循环迭代之外的所有子结果，因为该算法中的递归遵循严格的 n-1图案。但是，我暂时没有将其包含在我的代码中。

使用动态规划递归到迭代转换

Recursion to iteration conversion using dynamic programming

c#

memoization

dynamic-programming