为 spoj "BEHAPPY" 制定背包式解决方案？
Formulating a knapsack style solution for spoj "BEHAPPY"?
问题在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 的循环和初始化是什么？
提前致谢
首先删除所有最低要求。 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]]。你用 1 初始化 sol[0, M]，其余为 0。
您的解决方案将是 sol[N+1, 0].
如果你迭代地做，你只需要最后一行。
问题在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 的循环和初始化是什么？
提前致谢
首先删除所有最低要求。 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]]。你用 1 初始化 sol[0, M]，其余为 0。
您的解决方案将是 sol[N+1, 0].
如果你迭代地做，你只需要最后一行。