4

我试图找到并解决UVA #11450的动态编程方法的递归关系。作为免责声明，这是我大部分完成但对分析感到困惑的家庭作业的一部分。

这是我的（工作）代码：

int shop(int m, int c, int items[][21], int sol[][20]) {
    if (m < 0) return NONE;                  // No money left
    if (c == 0) return 0;                    // No garments left
    if (sol[m][c] != NONE) return sol[m][c]; // We've been here before

    // For each model of the current garment
    for (int i = 1; i <= items[c-1][0]; i++) {
        // Save the result
        int result = shop(m-items[c-1][i], c-1, items, sol);

        // If there was a valid result, record it for next time
        if (result != NONE) sol[m][c] = max(sol[m][c], result+items[c-1][i]);
    }

    return sol[m][c];
}

我在分析的几个方面遇到问题：

  • 基本操作是什么？我最初的反应是减法，因为每次调用函数时，我们都会从 C 中减一。
  • 由于递归调用在循环内，这是否仅意味着递归关系中的乘法？
  • 我如何将它使用动态表的事实考虑到递归关系中？我知道使用表格时有些问题会分解成线性问题，但我不确定这个问题是如何分解的。

我知道复杂性（根据Algorithmist）是 O(M*C*max(K)) ，其中 K 是每件衣服的模型数，但我正在努力向后工作以获得递归关系。这是我的猜测：

S(c) = k * S(c-1) + 1, S(0) = 0

但是，这没有考虑到 M。

想法？

4

1 回答 1

0

您可以将每个 DP 状态(m,c)视为图的一个顶点，其中对状态的递归调用(m-item_i,c-1)是从(m,c)到的边(m-item_i,i)。

递归的记忆意味着你只从一个顶点开始搜索一次，并且只处理一次它的传出边。因此，您的算法本质上是对该图的线性搜索，并且具有复杂性O(|V|+|E|)。有 M*C 个顶点max(K)，每个顶点最多有边，因此您可以将边数限制为O(M*C*max(K)).

于 2013-05-08T18:45:17.030 回答