algorithm - 为 spoj "BEHAPPY"制定背包式解决方案？

Question

问题在 problem 中描述，我一直在努力达成上述问题的迭代dp解决方案。 根据我的编码经验，我可以猜到，它应该具有三个维度，每个状态由 :-

M = Gifts not distributed yet.
N = first N girlfriends available (Similar to 0-1 Knapsack)
C = Maximum gifts allowable for current girlfriend.  

现在为 M=0,N,C 初始化(即当还有 0 个礼物要分发时)

      1 2 3 4 (girlfriends)
    0
    1
    2
    3
   (Capacity)

我似乎有一个问题，在 k=0 时初始化，因为对女朋友的礼物有上下限，因此偏离了只有最大限制的标准背包(不考虑背包找到最佳解决方案，这里我考虑所有可能的解决方案)

当然，我在这里可能完全走错了路，如果你觉得是这样，那么这 3 个状态变量 dp 的递归和初始化是什么？

提前致谢

Answer 1

首先删除所有最低要求。 M -= sum(A[i]) 和 B[i] -= A[i]。这些是最小值，因此我们无需四处移动，只需分配它们并将它们从计算中取出即可。

现在您的解决方案矩阵 sol[g, m] 是您在还剩 m 个礼物的情况下解决前 g 个女朋友的方法数。 sol[g,m] = sum(sol[g-1, m-j], j= [0..B[g-1]]。您将 sol[0, M] 初始化为 1 和其余为 0。 您的解决方案将是 sol[N+1, 0]。

如果你迭代地做，你只需要最后一行。