subset-sum

0热度

2回答

所以我想知道如何计算背包问题的所有解决方案。也就是说，我有兴趣从一组最大尺寸为K的数字中找到可能的子集数量。例如，我们有一组尺寸为{3,2,5,6,7}的项目和最大尺寸为K = 13，所以解为{5,6,2}和{6,7}。另一方面有两个解决方案;我想我的动态编程算法报告有两种可能的解决方案。

0热度

1回答

萨姆在阵列的任何k个元素的若干

设计的算法，给定n个整数的集合S和其他整数x，判断是否不存在K的（N> K> 2）元素S的总和恰好是x。请给出您的运行时间算法我一直在准备面试，而且我遇到了这个算法。我已经解决了问题中指定了k的问题。像2或3.但我找不到答案，我可能会解决任何可能存在的k。我试图用动态编程来解决它，但没有得到结果。谁可以帮我这个事。

5热度

1回答

查找整数数组的子集是否存在的有效算法，其所有元素的异或是给定值？

我有一个正整数数组- {1,5,8,2,10}和一个给定的值7. 我需要找到数组的子集是否存在，使得它的元素的XOR是值7 在这种情况下，子集是{5,2}，因为5 xor 2是7. 一个天真的解决方案是找到所有的子集并检查是否存在解决方案。我想要一些算法比天真更好。注： - 我只需要找出是否存在解决方案。我不需要找到子集。

0热度

4回答

从给定数量的元素获得阵列的所有独特组合

我想要一种方法来获得给定数组长度的所有给定数字的所有组合。在我的项目中，数组大小通常为7.因此，我编写了一个像这样的测试代码，以查看是否可以获得所有需要的组合。最重要的部分是每个结果数组必须是唯一的，最大的数组大小必须是7 <?php $numbers = [1, 2, 3, 4, 5, 6, 7]; $arraysize = 7; $subset = []; $count = co

1热度

1回答

子集总和为负值

我想知道如何处理负值和负值目标，现在我的程序在负值给这些变量时给出索引超出界限的错误。我需要我的hasSum函数对这个项目使用负值，我不能仅仅假设为正值。 import java.util.Stack; import java.util.Scanner; public class subsetSum { static Scanner input = new Scanner(Syst

2热度

5回答

在Prolog中对列表进行分区

我正在尝试创建一个Prolog谓词，其中给定一个列表，可以看出列表是否可以拆分成两个总计为相同数量的列表。我有一个工作列表总和谓词，所以我在分区谓词中使用它。我首先尝试对谓词进行编码，以查看列表的第一个元素是否等于列表的其余部分的总和（[2,1,1]）。这就是我对这种情况的看法。 partitionable([X|Y]) :- sum([X],SUM), sum([Y],SU

0热度

1回答

如何使用动态编程查找总和达到目标值的所有子集C

因此，我一直在尝试使用动态编程来完成子集总和问题的一个变体。那么，我的目标是为举例来说，能有 m = 25 // Target value n = 7 // Size of input set 的输入和输入设为例如{1, 3, 4, 6, 7, 10, 25}。所以想要的输出会像 {1, 3, 4, 7, 10} and {25}. 下面是代码 #include <stdio.h> #i

3热度

1回答

subset sum找到加起来的数字的所有子集

我一直在学习动态规划，并且我想通过打印出加起来的所有子集来进一步考虑经典的子集求和问题。我该如何去做这件事？截至目前，我知道如何根据打印true或false是否存在加起来它 public static boolean hasSum(int [] array, int sum) { int len = array.length; boolean[][] table = new

1热度

1回答

子集总和的方法总数的复发关系

我想找出在子集总和问题中达到目标的总数。以下是我的方法。如果'j'个元素的总和等于'i'，则DP [i，j]为1，否则为0，其中'a'为输入。所以， DP[i, j] = DP[i, j-1] + DP[i - a[j], j-1] 对于输入[10，13，15，18，20，15]和目标= 30 ;我们正在寻找DP [30,6]作为答案。我能够得到它与递归（http://ideone.com

2热度

2回答

错误Subset sum in O（n^2）

我知道这个代码/逻辑对于解决子集和问题是错误的，但似乎无法理解为什么。计算所有可能的子集的总和，并检查是否有任何等于所需的总和。这将在O（n^2）中完成，这显然是错误的，因为我可以通过DP O（n * sum）解决这个问题。谢谢。 int main() { long long int t,n,i,j; scanf("%lld",&t); while(t--)