2

我正在编写一些动态编程的复习材料。我需要想出应该如何划分子问题，计算出基本情况，并想出递归公式。

给定 n 个正整数 a1,a2,...,an、一个数字 k 和一个目标 W，我们想要选择一个子集 T，其中恰好有 k 个元素的总和最接近 W。每个元素只能选择一次。用 3 个参数定义一个子问题（即 C[x,y,z] = ...）。

我只使用过一些动态编程示例，并且从未使用过需要 3 个参数来定义子问题的示例。我真的迷路了。如果有人能发光，那就太好了。

我对子问题应该是什么的最佳猜测是：

C[x,y,z] = x 来自 {a1,...ay} 的元素数，其中总和正好是 z

但我不知道这是否正确。

4

2 回答 2

2

将其分解为三个参数的一种方法是：

x: maximum index of item considered for inclusion in subset
n: number of items in subset
s: sum of subset

基本情况是 C[0,0,0] = true，C[0,i > 0,j > 0] = false

递归情况是：

C[i,n+1,s+a_i] = C[i-1,n,s]  // use item i
C[i,n,s] = C[i-1,n,s] // dont use item i

这使用空间 O(n^2 * max(a_i)) （可以通过丢弃使用时的 C[i, , ] 减少到 O(n*max(a_i))）

然后只需在 z 附近搜索 C[n,i,j] 以获得最终答案。

作为一个循环...

for (int i = 1; i <= n; i++)
{
    C[i,n+1,s+a_i] ||= C[i-1,n,s];
    C[i,n,s] ||= C[i-1,n,s];
}

作为递归函数：

bool C(int maxindex, int size, int sum)
{
    if (memoize(maxindex, size, sum))
         return cached;

    if (maxindex == 0)
        return (size == 0 && sum == 0);

    return
         C(maxindex-1, size-1, sum - A[maxindex]) ||  // version using A[maxindex]
         C(maxindex-1, size, sum); // version not using A[maxindex]
}
于 2012-06-27T01:35:17.830 回答
0

在这种情况下，我会让 C(x,y,z) 是一个布尔值，表示是否可以使用来自 {a1 ... ax} 的恰好 y 得到恰好 z 的总和。

虽然它不是完全相同的问题Wikipedia，但具有针对各种类似问题的动态编程解决方案和解释。也许这会给你一些想法。

于 2012-06-27T01:28:32.943 回答