algorithm - 动态规划 - 书柜的最大排列

Question

我正在尝试解决一个问题，所以我不是在寻找代码，而是在寻找类似的算法，这样我就可以自己解决它。

我有 n 个书柜，每个书柜里都有 size 数量的书。我要将其中一些书柜移动到一个新房间，如下所示:

• 第一个书架总是会被移动；
• 我会保持新房间里书架的顺序(我不能在新房间里改变位置，一旦我选择了书架6，我就不能从中选择任何书了0 到 5);
• 书柜 i 不能放在书柜 i-1 或 i+1 旁边(例如:我不能放在?-4-5-?/?-5-6-?/?-4-5-6-?);

哪种书架配置可以提供最多的书？

我知道这是使用动态规划算法解决的，但我不确定是哪一个。我最初认为它类似于背包问题，但我没有书的限制所以它明显不同(至少我认为是这样)。

非常感谢任何建议!

Answer 1

制作一个数组int M[n] , 并设置 M[0] = b[0]因为第一个书架总是被移动。然后进行如下操作:

• 对于每个元素 b[i] , 其中i > 0 , 设置 M[i] = b[i]
• 返回 M 的元素在索引 j范围从 0至 i-2 ， 包括的;从 i-2 开始因为你不能拿走 b[i] 之前的书柜
• 设置M[i]到当前的最大值 M[i]和 M[j] + b[i] .这个表达式的意思是“我把 b[i] 附加到以 j 结尾的一系列书架上”
• 循环结束后，遍历M[] , 并找到最高的元素。这就是你的答案。
• 要打印书柜索引序列，从 M[] 的最大元素位置开始(比如 p )并打印 p
• 现在回顾 M职位k < p这样 M[k] = M[p] - b[p] .由于数组 M[] 的方式，至少会有一个这样的元素已建成。
• 打印 k , 设置 p=k , 并继续直到到达数组的开头。