algorithm - 需要帮助来了解Jewelry Topcoder解决方案的解决方案

Question

我是动态编程的新手，还不了解它可以解决的大多数类型的问题。因此，我在保持solution的Jewelry topcoder problem方面面临问题。

有人至少可以给我一些有关代码在做什么的提示吗？

最重要的是，此问题是subset-sum problem的变体吗？因为这就是我正在研究的解决这个问题的方法。

这两个函数实际上算什么？为什么我们实际上使用两个DP表？

void cnk() {
  nk[0][0]=1;
  FOR(k,1,MAXN) {
    nk[0][k]=0;
  }  

  FOR(n,1,MAXN) {
      nk[n][0]=1;
      FOR(k,1,MAXN) 
        nk[n][k] = nk[n-1][k-1]+nk[n-1][k];
     }
}

void calc(LL T[MAXN+1][MAX+1]) {
  T[0][0] = 1;
  FOR(x,1,MAX) T[0][x]=0;
  FOR(ile,1,n) {
    int a = v[ile-1];
    FOR(x,0,MAX) {
      T[ile][x] = T[ile-1][x];
      if(x>=a) T[ile][x] +=T[ile-1][x-a];
    }
  }
}

通过使用以下逻辑如何构造原始解决方案？

FOR(u,1,c) {
  int uu = u * v[done];
  FOR(x,uu,MAX)
  res += B[done][x-uu] * F[n-done-u][x] * nk[c][u];
  }
done=p;
}

任何帮助将不胜感激。

Answer 1

让我们首先考虑以下任务：


“给定一个N个小于K的N个正整数的向量V，求和的总和等于S的子集数”。


这可以在多项式时间内使用一些额外的内存通过动态编程来解决。

动态编程方法如下：
除了解决N和S的问题外，我们还将解决以下形式的所有问题：


“找到仅使用数字的前n≤N个来写和（s≤S）的方式的数目”。


这是动态编程解决方案的一个共同特征：您不仅可以解决原始问题，还可以解决整个相关问题系列。关键思想是可以从较容易设置的解决方案中有效地建立更困难的问题设置（即更高的n和s）的解决方案。

解决n = 0的问题是微不足道的（总和s = 0可以用一种方式表示-使用空集，而所有其他总和不能以任何方式表示）。
现在考虑我们已经解决了直到某个n的所有值的问题，并且我们在矩阵A中拥有了这些解决方案（即A [n] [s]是使用前n个元素写和s的方式的数目） 。

然后，我们可以使用以下公式找到n + 1的解：

A [n + 1] [s] = A [n] [s-V [n + 1]] + A [n] [s]。

确实，当我们使用前n + 1个数字写和时，我们可以包括V [n + 1]（不包括第n + 1个项）。

这就是calc函数的计算结果。 （cnk函数使用Pascal规则计算二项式系数）

注意：通常，如果最后我们只想回答初始问题（即，对于N和S），则数组A可以是一维的（长度为S）-这是因为无论何时尝试构造n + 1的解，我们只需要n的解，而不是较小的值。



这个问题（此答案中最初指出的那个问题）确实与subset sum problem（找到总和为零的元素子集）有关。

如果我们对所使用整数的绝对值有合理的限制（可以分配一个辅助数组来表示所有可能的和），则可以应用类似类型的动态规划方法。

在零和问题中，我们实际上对计数不感兴趣，因此A数组可以是布尔数组（指示总和是否可达到）。

另外，如果存在辅助阵列B，则可以使用该辅助阵列B来重建解决方案。

现在，重复将如下所示：

if (!A[s] && A[s - V[n+1]]) {
    A[s] = true;

    // the index of the last value used to reach sum _s_,
    // allows going backwards to reproduce the entire solution
    B[s] = n + 1; 
}

注意：实际的实现需要处理负和的额外注意事项，负和不能直接表示数组中的索引（可以通过考虑最小可及值来移动索引，或者，如果使用C / C ++，则可以使用技巧）可以应用此答案中描述的内容： https://stackoverflow.com/a/3473686/6184684）。



我将详细说明上述想法如何应用于 TopCoder problem及其问题中链接的 solution。

B和F矩阵。

首先，请注意解决方案中B和F矩阵的含义：


B [i] [s]表示仅使用最小的i个项目求和s的方式的数量
F [i] [s]表示仅使用最大的i个项目求和s的方式的数量


实际上，在按升序（对于B）和降序（对于F）对珠宝首饰值数组进行排序之后，使用 calc函数计算了两个矩阵。

没有重复的情况下的解决方案。

首先，使用以下示例考虑没有重复珠宝值的情况： [5, 6, 7, 11, 15]。

为了提醒您答案，我将假定该数组是按升序排序的（因此“第一个i项目”将引用最小的i个项目）。

给鲍勃的每个项目的价值都小于给弗兰克的每个项目，因此，在每个好的解决方案中，都会有一个分离点，这样鲍勃仅在该分离点之前接收项目，而弗兰克在该点之后仅接收项目。

为了计算所有解决方案，我们需要对所有可能的分离点求和。

例如，当分隔点在第3个和第4个项目之间时，Bob将仅从 [5, 6, 7]子数组中选择项目（最小的3个项目），而Frank将从其余的 [11, 12]子数组中选择项目（最大2个项目）。在这种情况下，两者都可以得到一个总和（s = 11）。每次两者都能获得总和时，我们需要乘以它们各自达到各自总和的方式数（例如，如果鲍勃可以以4种方式达到总和s，而弗兰克可以通过5种方式达到同一总和s ，则我们可以用该总和获得20 = 4 * 5个有效解，因为每个组合都是有效解）。

因此，我们将通过考虑所有分离点和所有可能的总和来获得以下代码：

res = 0;
for (int i = 0; i < n; i++) {
    for (int s = 0; s <= maxS; s++) {
        res += B[i][s] * F[n-i][s]
    }
}

但是，这里有一个微妙的问题。这通常会多次计数相同的组合（对于不同的分离点）。在上面提供的示例中，对于间隔 [5, 6] - [7, 11, 15]以及间隔 [5, 6, 7] - [11, 15]，都将计算总和为11的相同解。

为了缓解此问题，我们可以按“鲍勃选择的项目的最大价值”对解决方案进行划分（或者等效地，始终强迫鲍勃在其选择中包括当前分离下第一个子数组中价值最大的项目） 。

为了计算当Bob的最大价值项是第i个项（按升序排列）时达到sum的方式的数目，我们可以使用B [i] [s-v [i]]。之所以成立，是因为使用v [i]值项意味着需要使用前i个项的子集（索引0、1，... i-1）来表示总和s-v [i]。

这将实现如下：

res = 0;
for (int i = 0; i < n; i++) {
    for (int s = v[i]; s <= maxS; s++) {
        res += B[i][s - v[i]] * F[n - 1 - i][s];
    }
}

这离TopCoder上的解决方案越来越近（在该解决方案中， done对应于上面的 i和 uu = v[i]）。

扩展允许重复的情况。

当重复值可以出现在数组中时，当鲍勃最有价值的物品是v [i]时，直接计算解决方案的数量不再容易。我们还需要考虑Bob挑选的此类物品的数量。

如果有c个项目具有与v [i]相同的值，即v [i] = v [i + 1] = ... v [i + c-1]，而Bob挑选了u个此类项目，则他达到某一总和s的方式数等于：

comb(c, u) * B[i][s - u * v[i]]（1）

的确，这是成立的，因为可以从梳理c的所有c中选择u个项目，这些项目以comb（c，u）的方式具有相同的值。对于每个这样的u项选择，剩余总和为s-u * v [i]，这应该使用前i个项的子集（索引0、1，... i-1）表示。可以用B [i] [s-u * v [i]]方式完成。

对于弗兰克，如果鲍勃使用v [i]个项目中的u个，表示sum的方式数将等于：

F[n - i - u][s]（2）

实际上，由于Bob使用最小的i + u值，因此Frank可以使用任何最大的n-i-u值来求和s。

通过从上面组合关系（1）和（2），我们得出当Bob最有价值的项目是v [i]并且他选择u这样的项目时，Frank和Bob都具有和s的解的数目等于：

comb(c, u) * B[i][s - u * v[i]] * F[n - i - u][s]。

这正是给定的 solution实现的。

实际上，变量 done对应于上面的变量i，变量 x对应于和s，索引 p用于确定与v [done]值相同的 c项，并且遍历<使用cc>是为了考虑Bob挑选的此类物品的所有可能数量。