动态规划子集算法

Question

我正在为动态规划制定一些复习材料。我需要确定如何划分子问题、解决基本情况，并找出递归公式。

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

我只使用过一些动态规划示例，并且从未使用过需要在定义子问题中使用3个参数的例子。我真的迷失了。如果有人能帮我看清这个问题，那就太好了。

我的最佳猜测是：

C[x，y，z] = {a1，...ay}中x个元素的总和恰好为z

但我不知道这是否正确。

- Tesla

Answer 1

将这个问题分解成三个参数的一种方法是：

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))）

最终答案可以在C[n,i,j]中搜索j接近z的值。

作为一个循环...

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

- Andrew Tomazos

---

嗯，这个递归函数会是什么样子呢？我习惯于开发递归函数，并从那里转到伪代码。能够从这个中推导出来吗？大致如下：C[x,y,z] = { ... } - Tesla

@特斯拉：添加了循环和递归函数。 - Andrew Tomazos

Answer 2

在这种情况下，我会让C（x，y，z）成为一个布尔值，表示是否可能使用{a1 ... ax}中的恰好y个数得到恰好z的总和。

虽然它不是完全相同的问题Wikipedia，但它有动态规划解决方案，适用于各种类似的问题，并附有解释。也许这可以给你一些想法。

- Antimony