动态规划子集算法

Question

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

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

我只处理过几个动态编程示例，从未处理过定义子问题时需要3个参数的示例。我在这里真的迷路了。如果有人能发光，那就太好了。

我对子问题的最佳猜测是：

c[x， y， z]={a1，… ay}中的x个元素，其中总和正好是z

但我不知道这是否正确。

Answer 1

在这种情况下，我将让C（x， y， z）是一个布尔值，表示是否可以使用{a1… ax}中的y精确地求和z。

尽管这不是完全相同的问题，但维基百科为各种类似问题提供了动态编程解决方案，并提供了解释。也许这会给你一些想法。

Answer 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]=真，C[0，i

递归情况为：

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