时间戳

首页 > 解决方案 > 子集和问题，通过初始排序打破平局

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

问题描述

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

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

对于经典问题，我知道如何使用动态编程来解决，但为了打破平局，除了首先找到所有可能的子集然后选择具有最佳排序的子集之外，我想不出更好的方法。有任何想法吗？

标签： algorithmdynamic-programmingsubset-sum

解决方案

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

让有T个项目，第i 个项目将有= ，重量 = 。

在所有最大权重的子集中，我们将寻找具有最大项累计值的那个。我已将值设置为 2 的幂，以确保数组中第一个项目的优先级高于它的所有后继项目。

这是一个实际的例子：

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

项目 {8, 4, 2, 2}

值 {8, 4, 2, 1}

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

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

= 区间 [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）并且当且仅当 (DP [T][N] & v[i]) == v[i]。

推荐阅读