algorithm - 子集和问题，通过初始排序打破平局

Question

给定一组数字，找到子集 s.t.子集中所有数字的总和等于 N。通过元素的初始顺序打破所有可行子集之间的联系。假设数字是整数，并且存在这样的子集，其总和为N。

例如，给定一个数组[2, 5, 1, 3, 4, 5]并且N = 6，输出需要是{2, 1, 3}。虽然 {5, 1}、{2, 4} 和 {1, 5} 也是总和为 6 的子集，但我们需要按照数组中数字的顺序返回{2, 1, 3}。

对于经典问题，我知道如何使用动态规划来解决，但要打破僵局，除了首先找到所有可能的子集然后选择顺序最佳的子集之外，我想不出更好的方法。有什么想法吗？

Answer 1

我将尝试提供一种有趣的打破联系的方式。让我们为项目分配另一个值，让 i_th 项目的值被称为 v[i]。

有 T 项，第 i-th 项将有 = , 权重 = .

在最大权重的所有子集中，我们将寻找具有最大项目累积值的子集。我已将这些值设置为 2 的幂，以确保数组中排在首位的项优先于其所有后续项。

这是一个实际的例子:

考虑 N = 8，作为我们的限制权重。

项目{8、4、2、2}

值 {8, 4, 2, 1}

我们将有两个不同的子集，它们的权重总和 = 8, {8} 和 {4, 2, 2}。但是第一个的 accumulated_value = 8，另一个的 accumulated_value = 7，所以我们会选择 {8} 而不是 {4, 2, 2}。

现在的想法是制定一个考虑总值(value)的动态规划。

= 区间 [0, i] 中总权重 = W 的所有项目子集中的最大累加值。

我将给出解决方案的伪代码

Set all DP[i][j] = -infinity

DP[0][0] = 0

for(int weight = 0; weight <= N; ++weight ) 
{
    for(int item = 0; item < T; ++item ) 
    {
        DP[item][weight] = DP[item - 1][weight]; // not using the current item
        if( v[item] < weight ) continue;
        else 
        {
            DP[item][weight] = max( DP[item][weight], DP[item - 1][ weight - w[item]] + v[item])
        }
    }
}

运行算法后如何恢复项目真的很简单。DP[T][N] 将是 2 的幂之和(如果无法选择总和为 N 的项目，则为 -infinity)并且第 i-th 项目属于答案当且仅当 (DP[T][N] & v[i]) == v[i]。