subset-sum

1热度

2回答

子集大小为'k`的子集合是NPC吗？

我有一个Subset-Sum problem的变化，其中子集的大小是k，并且所有整数都是正数（而非零）。从网上可以看出，这个问题可以用伪多项式时间的动态规划来解决。我需要决定这个问题是NPC，还是在P（同时假设P!=NP）。我试图减少子集和问题，但有一个约束，所有整数必须大于零的问题。除此之外，我会用k填充零输入。问题的正式定义： L={<S1,S2,...,Sn,T,k>|There e

0热度

4回答

变子集琛的

鉴于3正整数n, k, and sum，准确地找到k不同的元素a_i，其中 a_i \in S, 1 <= i <= k, and a_i \neq a_j for i \neq j 和，S是集 S = {1, 2, 3, ..., n} 这样 \sum_{i=1}^{k}{a_i} = sum 我不数不想施加暴力（检查所有可能的组合）来解决由于指数复杂性导致的问题。有人能给我一个解决这个问题的另

4热度

3回答

子集与一个2675号码列表

我正在寻找一个问题的是/否回答是否可以有效解决问题。我相当肯定，目前我们可以使用的计算技术是不可能的。我很高兴知道我错了。所以这里什么都不做。我有一个2576数字的列表。我正在尝试在列表中找到总计为44576.54的数字组合。数字列表包含从5位数字（两位数字精度）到8位数字（两位数字精度）的数字。我会非常感谢您的帮助！

-1热度

1回答

子集和概率的变化。（多个约束）

让我给你上，我试图解决正常的子集和问题的变化的一个例子：给出的一组小号 = {1,2,3， 4,5,6,7,8,9}具有最大容量C0 = 40。此外，我们有上的3项不同子集附加3个约束小号： S1 = {2,3， 4}约束c1 = 5 S2 = {3 ，4,5,6}与约束C2 = 12 S3 = {7,8,9}与约束C3 = 25 的目标是找到的小号使得一个子集路口是possib： - （C4

1热度

2回答

R具有行限制的expand.grid

我有一个长度为N的数值向量x，并且想要创建以下所有集合的集合内和的向量：任何可能的x元素与最多M每个组合中的元素。我把一个缓慢的迭代方法放在一起;我在这里寻找的是一种不使用任何循环的方式。考虑我已经采用的方法，在下面的例子中有N = 5和M = 4 M <- 4 x <- 11:15 y <- as.matrix(expand.grid(rep(list(0:1), length(x))))

1热度

3回答

打印所有子集是总结到特定值

我是想有一段时间来找到所有元素（包括非连续）数组，总计达到特定值的： using System; namespace ProgrammingBasics { class Exercise { static void Main() { PrintArray(arr); SubarrayWithSum(); }

0热度

1回答

给定n个整数的列表，找到大于X的最小子集总和

给定数组形式的未分类整数集合，找到大于或等于常量整数x的最小子集总和。如： - 我们集{4 5 8 10 10}和x=15 所以最接近最小的子集总和x和>=x is {5 10} 我只能想到一个天真的算法，其中列出了集合的所有子集和检查，如果子集的总和并且最小或不是，但其指数算法和列出所有子集需要O（2^N）。我可以使用动态规划在多项式时间内解决它吗？

-1热度

3回答

查找给定的一组整数的总和达到给定总和的所有组合

我正在寻找对以下问题的答案。给定一组整数（无重复项）和一个和，找出该组元素的所有可能组合总和。解决方案顺序无关紧要（解{2，2，3}和{3，2，2}是相等的）。请注意，最终组合不需要是一个集合，因为它可以包含重复项。实施例：集{2,3,5} 萨姆10 结果： {2,2，2，2，2}，{2,2，3,3}，{2， 3，5}，{5，5} 我已经看过子集合问题以及币改变问题，但无法调整它们以适应我

1热度

1回答

找到最接近目标值的子集，如果算法找不到具有使用堆栈的精确总和的子集

private static Stack<Integer> temp = new Stack<Integer>(); public void populateSubset(int[] DATA, int fromIndex, int endIndex, int target) { if (sumInStack == target) { check = true ;

0热度

1回答

实现子集和与遗传算法

import java.util.Collections; import java.util.Vector; public class Metaheuristic { private static int[] DATA; private static int NUM_CHROMOSOMES ; private static int MAX_POWER;