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
当涉及更大的数字(特别是对于s)时，以下方法可能很有用，因此二维数组将是不必要的大数组，并且实际上只有几个w值用于计算结果。
这个想法：从w开始预先计算可能的w值，并针对每个i in [n, n-1, ..., 1]确定w_[i]的值，其中w_[i+1] >= s[i]没有重复。 然后循环i_n遍历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];
}
重要的是要了解，为了预先计算可能的 w 值并支持稀疏数据结构，一些空间和计算被"浪费"了。因此，这种方法对于s中值较小的大型数据集可能表现不佳，其中大多数w值可能是子结果。
经过一番思考，我意识到，如果空间是一个问题，你实际上可以扔掉除了前面的外循环迭代之外的所有子结果，因为该算法中的递归遵循严格的n-1模式。但是，我现在不将其包含在我的代码中。
您的方法不起作用，因为您的动态 programmig 状态空间(显然只有一个变量)与递归方法的签名不匹配。动态规划方法的目标应该是定义和填充状态空间，以便在需要时提供所有评估结果。在检查递归方法时，请注意F_recursion的递归调用可能会更改参数，n和w。这表明应使用二维状态空间。
第一个参数(显然限制了项目的范围)的范围可以从0到n，而第二个参数(显然是项目属性的总和)的范围可以从0到w。
您应该定义一个二维状态空间
int[,] value = new int[n,w];
为了容纳这些价值观。接下来，您应该将值初始化为未定义;您可以为此使用值Int32.MaxValue，因为如果计算具有一些不同值的最小值，它将以合适的方式运行。
接下来，该算法的迭代版本使用两个循环，它们以 forwad 方式迭代，这与递归迭代减少参数不同。
for (int i = 0; i < n; i++)
{
for (int j = 0; j < w; j++)
{
// logic for the recurrence relation goes here
}
}
在最里面的块中，您可以使用递归关系的修改版本。您访问存储在value中的值，而不是使用递归调用;不是返回值，而是将值写入value。
在语义上，这与记忆相同，但不是使用实际的递归调用，而是计算顺序断言必要的值始终存在，使得额外的逻辑变得不必要。
一旦状态空间被填满，你必须检查它的最后一个状态(即数组中第一个索引n-1的部分)，以确定整个输入的最大值。