堆垛与动态规划
基本上，我是想解决这个问题：
给出N个单位立方体砌块，找出较小数量的桩，以便使用所有的砌块。一堆不是立方体就是金字塔。例如，两个有效桩是使用64块的立方体4 *4 *4=64和使用30块的金字塔1²+2²+3²+4²=30。
但是，我找不到合适的角度来接近它。我觉得这类似于背包问题，但却找不到实现。
任何帮助都将不胜感激！
回答 1
Stack Overflow用户
发布于 2017-02-06 16:16:15
首先，我将给出一个递推关系，它允许递归地解决这个问题。给定N，让
SQUARE-NUMS
TRIANGLE-NUMS分别是{1,...,N}中正方形数和三角形数的子集。让PERMITTED_SIZES成为这些东西的统一体。请注意，正如1发生在PERMITTED_SIZES中一样，任何实例都是可行的，并产生一个非负最优。
伪码中的折叠函数可以递归地解决问题中的问题。
int MinimumNumberOfPiles(int N)
{
int Result = 1 + min { MinimumNumberOfPiles(N-i) }
where i in PERMITTED_SIZES and i smaller than N;
return Result;
}其思想是为项选择允许的bin大小，删除这些项(这会使问题实例更小)，并对较小的实例进行递归解决。为了避免对同一子问题的多重评估，要使用动态规划，可以使用一维状态空间，即数组A[N]，其中A[i]是i单元块所需的最小桩数。使用这个状态空间，这个问题可以迭代地解决如下。
for (int i = 0; i < N; i++)
{
if i is 0 set A[i] to 0,
if i occurs in PERMITTED_SIZES, set A[i] to 1,
set A[i] to positive infinity otherwise;
}这初始化了预先已知的状态，并对应于上述递归中的基本情况。接下来，使用下面的循环填充缺失的状态。
for (int i = 0; i <= N; i++)
{
if (A[i] is positive infinity)
{
A[i] = 1 + min { A[i-j] : j is in PERMITTED_SIZES and j is smaller than i }
}
}所需的最优值将在A[N]中找到。请注意，此算法只计算最小桩数，而不计算桩本身；如果需要适当的分区，则必须通过回溯或维护附加的辅助数据结构来找到。
总之，只要知道PERMITTED_SIZES，问题就可以在O(N^2)步骤中解决，因为PERMITTED_SIZES最多包含N值。
这个问题可以看作是对棒材切割问题的一种适应，其中每个平方或三角形大小都有值0，而其他大小都有值1，目标是最小化总价值。
总之，从输入生成PERMITTED_SIZES需要额外的计算成本。
更准确地说，一旦A被填充，相应的桩的选择就可以通过如下的回溯来生成。
int i = N; // i is the total amount still to be distributed
while ( i > 0 )
{
choose j such that
j is in PERMITTED_SIZES and j is smaller than i
and
A[i] = 1 + A[i-j] is minimized
Output "Take a set of size" + j; // or just output j, which is the set size
// the part above can be commented as "let's find out how
// the value in A[i] was generated"
set i = i-j; // decrease amount to distribute
}https://stackoverflow.com/questions/42071324
复制相似问题
腾讯云开发者
